Previous |  Up |  Next

Article

Title: NP-hardness results for intersection graphs (English)
Author: Kratochvíl, Jan
Author: Matoušek, Jiří
Language: English
Journal: Commentationes Mathematicae Universitatis Carolinae
ISSN: 0010-2628 (print)
ISSN: 1213-7243 (online)
Volume: 30
Issue: 4
Year: 1989
Pages: 761-773
.
Category: math
.
MSC: 05C75
MSC: 05C85
MSC: 05C99
MSC: 68Q25
MSC: 68R10
idZBL: Zbl 0697.05052
idMR: MR1045907
.
Date available: 2008-06-05T21:41:05Z
Last updated: 2012-04-28
Stable URL: http://hdl.handle.net/10338.dmlcz/106799
.
Reference: [BL] 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. MR 0433962
Reference: [Bou] A. Bouchet: Reducing prime graphs and recognizing circle graphs.Combinatorica 7 (1987), 243-254. Zbl 0666.05037, MR 0918395
Reference: [EET] G. Ehrlich S. Even R. E. Tarjan: Intersection graphs of curves in the plane.J. Combin. Theory Ser. B 21 (1976), 8-20. MR 0505857
Reference: [FPP] H. Fraysseix J. Pach R. Pollack: Small sets representing Fáry embeddings of planar graphs.Proceedings STOC 1988.
Reference: [Fou] J. C. Fournier: Une caractenzation dęs graphes de cordes.C.R. Acad. Sci. Paris 286A (1978), 811-813. MR 0498269
Reference: [FG] D. F. Fulkerson O. A. Gross: Incidence matrices with the consecutive 1 's property.Bull. Amer. Math. Soc. 70 (1965), 681-684.
Reference: [Gav] F. Gavril: Algorithms for a maximum clique and maximum independent set of a circle graph.Networks 4 (1973), 261-273. MR 0340106
Reference: [GH] P. C. Gilmore A. J. Hoffman: A characterization of interval graphs and of comparability graphs.Canad. Math. J. 16 (1964), 539-548. MR 0175811
Reference: [KGK] J. Kratochvíl M. Goljan P. Kučera: String graphs.Academia, Prague 1986. MR 0865778
Reference: [KM] J. Kratochvíl J. Matoušek: Intersection graphs of segments.KAM Series, Charles University Prague, 1989.
Reference: [KK] 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.
Reference: [Kra1] J. Kratochvíl: String graphs II Recognizing siring graphs is NP-hard.to appear in J. Comb. Theory Ser. B. MR 0737032
Reference: [Kra2] J. Kratochvíl: A special planar satisfiability problem and some consequences of its NP-completeness.submitted.
Reference: [LB] 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. MR 0139159
Reference: [Sin] F. W. Sinden: Topology of thin film RC-circuits.Bell System Tech. J. (1966), 1639-1662. Zbl 0144.45601
Reference: [Tuc] A. C. Tucker: An algorithm for circular-arc graphs.SIAM J. Computing 31. 2 (1980), 211-216. MR 0557822
.

Files

Files Size Format View
CommentatMathUnivCarol_030-1989-4_19.pdf 1.355Mb application/pdf View/Open
Back to standard record
Partner of
EuDML logo