Recognizing graphs with fixed interval number is NP-complete

DOI10.1016/0166-218X(84)90127-6zbMATH Open0554.68041OpenAlexW2076027639MaRDI QIDQ760213FDOQ760213

Authors: 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

Recommendations

• On interval representations of graphs
• The Total Interval Number of a Graph II: Trees and Complexity
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Interval graph representation with given interval and intersection lengths
• Interval graph representation with given interval and intersection lengths

zbMATH Keywords

graph algorithmNP-completenessinterval numberinterval graphinterval representation

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (32)

• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• Optimization problems in multiple subtree graphs
• On the interval number of random graphs
• Using fractional primal-dual to schedule split intervals with demands
• The interval number of a planar graph is at most three
• Interval graph representation with given interval and intersection lengths
• On an extremal problem concerning the interval number of a graph
• On local structures of cubicity 2 graphs
• Interval numbers of powers of block graphs
• On interval representations of graphs
• Interval graph representation with given interval and intersection lengths
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• On the parameterized complexity of multiple-interval graph problems
• Extracting constrained 2-interval subsets in 2-interval sets
• An interval chaos insight to iterative decomposition method for Rossler differential equation by considering stable uncertain coefficients
• Some new results on bar visibility of digraphs
• The interval number of a planar graph: Three intervals suffice
• On the unit interval number of a graph
• A graph-theoretic barcode ordering model for linked-reads
• Recognizing unit multiple interval graphs is hard
• Edge-intersection graphs of grid paths: the bend-number
• Three ways to cover a graph
• On the computational complexity of 2-interval pattern matching problems
• Fast diameter computation within split graphs
• The maximum clique problem in multiple interval graphs
• Irredundancy in multiple interval representations
• Recognizing tough graphs is NP-hard
• Tree loop graphs
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Precedence thinness in graphs
• Representations of graphs and networks (coding, layouts and embeddings)

This page was built for publication: Recognizing graphs with fixed interval number is NP-complete

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