×

zbMATH — the first resource for mathematics

Complexity of representation of graphs by set systems. (English) Zbl 0473.68064

MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C99 Graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beineke, L.W., Derived graphs and digraphs, Beiträge zur graphen-theorie, Leipzig, 17-33, (1968) · Zbl 0179.29204
[2] Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029
[3] Bermond, J.C.; Meyer, J.C., Graphs représentent des arces d’un multigraphe, J. math. pures appl., 9, 52, 229-308, (1973) · Zbl 0219.05078
[4] Erlich, G.; Even, S.; Tarjan, R.E., Intersection graphs of curves in the plane, J. combinatorial theory, 21, B, 8-20, (1976) · Zbl 0348.05113
[5] Erdös, P.; Goodman, A.W.; Posa, L., The representation of graphs by set intersections, Canad. math. J, 18, 106-612, (1966) · Zbl 0137.43202
[6] Garey, M.R.; Johnson, D.S.; Stockmayer, L., Some simplified NP-complete graph problems, Theoret. comput. sci, 1, 237-267, (1976) · Zbl 0338.05120
[7] Grimmet, G.R.; McDiarmid, C.J.H., On colouring random graphs, Math. proc. camb. phil. soc, 77-313, (1975) · Zbl 0297.05112
[8] Fulkerson, D.R.; Gross, D.A., Incidence matrices and interval graphs, Pacific J. math, 15, 835-855, (1965) · Zbl 0132.21001
[9] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[10] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman San Francisco · Zbl 0411.68039
[11] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[12] Marzewski, E., Sur deux proprietes des classes d’ensembles, Fund. math, 33, 303-307, (1945) · Zbl 0060.12508
[13] Papadimitrou, C.H., The NP-completeness of the bandwidth minimization problem, Comput, 16, 263-270, (1976) · Zbl 0321.65019
[14] Poljak, S.; Rödl, V., Set systems determined by intersections, Discrete math, 34, 173-184, (1981) · Zbl 0474.05060
[15] Kou, L.T.; Stockmeyer, L.J.; Wong, C.K., Covering edges by cliques with regard to keyword conflicts and intersection graphs, Comm. ACM, (1978) · Zbl 0367.68035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.