| Title:
|
INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs (English) |
| Author:
|
Kratochvíl, Jan |
| Author:
|
Nešetřil, Jaroslav |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
31 |
| Issue:
|
1 |
| Year:
|
1990 |
| Pages:
|
85-93 |
| . |
| Category:
|
math |
| . |
| MSC:
|
05C85 |
| MSC:
|
05C99 |
| MSC:
|
68Q25 |
| MSC:
|
68R10 |
| idZBL:
|
Zbl 0727.05056 |
| idMR:
|
MR1056173 |
| . |
| Date available:
|
2008-06-05T21:42:05Z |
| Last updated:
|
2012-04-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/106821 |
| . |
| Reference:
|
[EET] Ehrlich G., Even S., Tarjan R. E.: Intersection graphs of curves in the plane.J. Combin. Th. Ser. B 21 (1976), 8-20. Zbl 0348.05113, MR 0505857 |
| Reference:
|
[FPP] de Fraysseix H., Pach J., Pollack R.: Small sets supporting Fáry embeddings of planar graphs.STOC 1988. |
| Reference:
|
[Gav] Gavril F.: Algorithms for a maximum clique and maximum independent set of a circle graph.Networks 4 (1973), 261-273. MR 0340106 |
| Reference:
|
[GJ] Garey M. R., Johnson D. S.: Computers and Intractability: A Guide to the Theory of NP-completeness.Freeman, San Francisco, 1979. Zbl 0411.68039, MR 0519066 |
| Reference:
|
[Kra1] Kratochvíl J.: String graphs I. The number of critical nonstring graphs is infinite.(to appear in J. Combin. Th. Ser. B). MR 1109419 |
| Reference:
|
[Kra2] Kratochvíl J.: String graphs II. Recognizing string graphs in NP-hard.(to appear in J. Combin. Th. Ser. B). MR 0737032 |
| Reference:
|
[KGK] Kratochvíl J., Goljan M., Kučera P.: String graphs.Rozpravy československé akademie věd, ŘMPV 96, No. 3, Academia, Prague, 1986. MR 0865778 |
| Reference:
|
[KM] Kratochvíl J., Matoušek J.: Intersections graphs of segments.submitted. |
| Reference:
|
[KM2] Kratochvíl J., Matoušek J.: NP-hardness results for intersection graphs.Comment. Math. Univ. Carolinae 30 (1989), 761-773. MR 1045907 |
| Reference:
|
[MP] Middendorf M., Pfeiffer F.: Max clique problem in classes of string graphs.preprint Univ. Bonn (1988). MR 1189857 |
| Reference:
|
[S] Sinden F. W.: Topology of thin film RC circuits.Bell System Tech. J. (1966), 1639-1662. Zbl 0144.45601 |
| Reference:
|
[V] Valiant L. G.: Universality considerations in VLSI circuits.IEEE Trans. Comput. 30 (1981), 135-140. Zbl 0455.94046, MR 0605722 |
| . |
