Recognizing graphs with fixed interval number is NP-complete

DOI10.1016/0166-218X(84)90127-6zbMath0554.68041OpenAlexW2076027639MaRDI QIDQ760213

Douglas B. West, David B. Shmoys

Publication date: 1984

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

Full work available at URL: https://doi.org/10.1016/0166-218x(84)90127-6

zbMATH Keywords

graph algorithmNP-completenessinterval graphinterval numberinterval representation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

On an extremal problem concerning the interval number of a graph, On the computational complexity of 2-interval pattern matching problems, Irredundancy in multiple interval representations, Recognizing \(d\)-interval graphs and \(d\)-track interval graphs, Using fractional primal-dual to schedule split intervals with demands, On the unit interval number of a graph, Tree loop graphs, On the parameterized complexity of some optimization problems related to multiple-interval graphs, On Local Structures of Cubicity 2 Graphs, Three ways to cover a graph, Unnamed Item, Edge-intersection graphs of grid paths: the bend-number, Interval numbers of powers of block graphs, On the interval number of random graphs, The interval number of a planar graph is at most three, Representations of graphs and networks (coding, layouts and embeddings), Extracting constrained 2-interval subsets in 2-interval sets, Optimization problems in multiple subtree graphs, On interval representations of graphs, On the parameterized complexity of multiple-interval graph problems, Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review, The interval number of a planar graph: Three intervals suffice, Precedence thinness in graphs, The maximum clique problem in multiple interval graphs, Fast Diameter Computation within Split Graphs

Cites Work

• Unnamed Item
• The interval number of a planar graph: Three intervals suffice
• The interval number of a complete multipartite graph
• Extremal values of the interval number of a graph. II
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On double and multiple interval graphs
• Extremal Values of the Interval Number of a Graph
• Polynomial Complete Consecutive Information Retrieval Problems
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• Two-Processor Scheduling with Start-Times and Deadlines