NP-hardness results for intersection graphs

Jan Kratochvíl; Jiří Matoušek

Commentationes Mathematicae Universitatis Carolinae (1989)

  • Volume: 030, Issue: 4, page 761-773
  • ISSN: 0010-2628

How to cite

top

Kratochvíl, Jan, and Matoušek, Jiří. "NP-hardness results for intersection graphs." Commentationes Mathematicae Universitatis Carolinae 030.4 (1989): 761-773. <http://eudml.org/doc/17790>.

@article{Kratochvíl1989,
author = {Kratochvíl, Jan, Matoušek, Jiří},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {NP-hard problem; string graph; intersection graph},
language = {eng},
number = {4},
pages = {761-773},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {NP-hardness results for intersection graphs},
url = {http://eudml.org/doc/17790},
volume = {030},
year = {1989},
}

TY - JOUR
AU - Kratochvíl, Jan
AU - Matoušek, Jiří
TI - NP-hardness results for intersection graphs
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1989
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 030
IS - 4
SP - 761
EP - 773
LA - eng
KW - NP-hard problem; string graph; intersection graph
UR - http://eudml.org/doc/17790
ER -

References

top
  1. K. S. Booth G. S. Lucker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. Syst. Sci 13 (1976), 255-265. (1976) MR0433962
  2. A. Bouchet, Reducing prime graphs and recognizing circle graphs, Combinatorica 7 (1987), 243-254. (1987) Zbl0666.05037MR0918395
  3. G. Ehrlich S. Even R. E. Tarjan, Intersection graphs of curves in the plane, J. Combin. Theory Ser. B 21 (1976), 8-20. (1976) MR0505857
  4. H. Fraysseix J. Pach R. Pollack, Small sets representing Fáry embeddings of planar graphs, Proceedings STOC 1988. (1988) 
  5. J. C. Fournier, Une caractenzation dęs graphes de cordes, C.R. Acad. Sci. Paris 286A (1978), 811-813. (1978) MR0498269
  6. D. F. Fulkerson O. A. Gross, Incidence matrices with the consecutive 1 's property, Bull. Amer. Math. Soc. 70 (1965), 681-684. (1965) 
  7. F. Gavril, Algorithms for a maximum clique and maximum independent set of a circle graph, Networks 4 (1973), 261-273. (1973) MR0340106
  8. P. C. Gilmore A. J. Hoffman, A characterization of interval graphs and of comparability graphs, Canad. Math. J. 16 (1964), 539-548. (1964) MR0175811
  9. J. Kratochvíl M. Goljan P. Kučera, String graphs, Academia, Prague 1986. (1986) MR0865778
  10. J. Kratochvíl J. Matoušek, Intersection graphs of segments, KAM Series, Charles University Prague, 1989. (1989) 
  11. J. Kratochvíl M. Křivánek, Satisfiability of almost satisfied formulas, (in Czech), in Proceedings Czechoslovak Conference on Graph Theory, Hrubá Skála 1989., Acta Univ. Hamm. Ham. 1 (1989), 11. (1989) 
  12. J. Kratochvíl, String graphs II Recognizing siring graphs is NP-hard, to appear in J. Comb. Theory Ser. B. MR0737032
  13. J. Kratochvíl, A special planar satisfiability problem and some consequences of its NP-completeness, submitted. 
  14. C. B. Lekkerker J. C. Boland, Representation of finite graphs by a set of intervals on the real line, Fund. Math 51 (1962), 45-64. (1962) MR0139159
  15. F. W. Sinden, Topology of thin film RC-circuits, Bell System Tech. J. (1966), 1639-1662. (1966) Zbl0144.45601
  16. A. C. Tucker, An algorithm for circular-arc graphs, SIAM J. Computing 31. 2 (1980), 211-216. (1980) MR0557822

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.