Some complexity results about threshold graphs

DOI10.1016/0166-218X(94)90214-3zbMath0802.90109WikidataQ127372854 ScholiaQ127372854MaRDI QIDQ1327235

Margot, François

Publication date: 15 June 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

cliqueNP-complete\(k\)-cyclic schedulingthreshold completion problemthreshold problemsthreshold subgraph problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items

Deleting edges to restrict the size of an epidemic: a new application for treewidth ⋮ Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs ⋮ Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes ⋮ Complexity classification of some edge modification problems ⋮ NP-completeness results for edge modification problems ⋮ Min-max subsequence problems in multi-zone disk recording ⋮ NP-completeness results for some problems on subclasses of bipartite and chordal graphs ⋮ Complexity of min-max subsequence problems ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Threshold hypergraphs
• Cyclic scheduling of offweekends
• Hamiltonian threshold graphs
• The Complexity of the Partial Order Dimension Problem
• Sufficient Conditions for Graphs to Have Threshold Number 2
• Two-Processor Scheduling with Start-Times and Deadlines
• Threshold Numbers and Threshold Completions