Recognizing graphs with fixed interval number is NP-complete
Authors:
- David B. ShmoysDSDavid B. Shmoys
- 1 July 1984
- journal article
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 8 (3) , 295-305
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- The interval number of a complete multipartite graphDiscrete Applied Mathematics, 1984
- The interval number of a planar graph: Three intervals sufficeJournal of Combinatorial Theory, Series B, 1983
- Split GenesScientific American, 1981
- Extremal Values of the Interval Number of a GraphSIAM Journal on Algebraic Discrete Methods, 1980
- Extremal values of the interval number of a graph, IIDiscrete Mathematics, 1979
- On double and multiple interval graphsJournal of Graph Theory, 1979
- Covering edges by cliques with regard to keyword conflicts and intersection graphsCommunications of the ACM, 1978
- Polynomial Complete Consecutive Information Retrieval ProblemsSIAM Journal on Computing, 1977
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976
- ON THE TOPOLOGY OF THE GENETIC FINE STRUCTUREProceedings of the National Academy of Sciences, 1959