Some complexity results about threshold graphs

DOI10.1016/0166-218X(94)90214-3MaRDI QIDQ1327235zbMATH OpenWikidataFDO

Authors François Margot

Publication date 15 June 1994

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

Full work available at URL https://doi.org/10.1016/0166-218X(94)90214-3

zbMATH Keywords

\(k\)-cyclic schedulingcliqueNP-completethreshold completion problemthreshold problemsthreshold subgraph problem

Mathematics Subject Classification ID

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

Recommendations

• NP-completeness results for some problems on subclasses of bipartite and chordal graphs
• Graph Sandwich Problems
• scientific article; zbMATH DE number 89406
• The complexity of some problems related to GRAPH 3-COLORABILITY

Cites work

• Cyclic scheduling of offweekends
• Hamiltonian threshold graphs
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• Sufficient Conditions for Graphs to Have Threshold Number 2
• The Complexity of the Partial Order Dimension Problem
• Threshold hypergraphs
• Threshold Numbers and Threshold Completions
• Two-Processor Scheduling with Start-Times and Deadlines

Cited in

(19)

• Complexity of min-max subsequence problems
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
• On dynamic threshold graphs and related classes
• A sharp threshold phenomenon in string graphs
• Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
• NP-completeness results for edge modification problems
• The simple graph threshold number (r,s,a,t) when r 3 is odd and a 2 is even
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• scientific article; zbMATH DE number 5575414 (Why is no real title available?)
• Enumerating threshold graphs and some related graph classes
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• scientific article; zbMATH DE number 2230201 (Why is no real title available?)
• Complexity classification of some edge modification problems
• Min-max subsequence problems in multi-zone disk recording
• The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
• Some Properties of Chain and Threshold Graphs
• The circular balancing problem
• NP-completeness results for some problems on subclasses of bipartite and chordal graphs

This page was built for publication: Some complexity results about threshold graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1327235)