| 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 |
| . |
