✦ LIBER ✦

The max clique problem in classes of string-graphs

✍ Scribed by M. Middendorf; F. Pfeiffer

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 378 KB
Volume: 108
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90688-c

No coin nor oath required. For personal study only.

✦ Synopsis

Middendorf, M., F. Pfeiffer, The max clique problem in classes of string-graphs, Discrete Mathematics 108 (1992) 365-372. A string-graph is an intersection graph of a set of curves in the plane. Investigating the complexity of the max clique problem for some classes of string-graphs we obtain NPcompleteness results on one hand and polynomial time algorithms on the other hand for string-graph-classes of at first sight surprising similarity.

📜 SIMILAR VOLUMES

The performance of an eigenvalue bound o

The performance of an eigenvalue bound on the max-cut problem in some classes of graphs

✍ C. Delorme; S. Poljak 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 683 KB

Delorme, C. and S. Poljak, The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, Discrete Mathematics 111 (1993) 145-156. The authors earlier introduced a number q(C), which gives a well-computable upper bound on the maximum bipartite subgraph of a graph or, more

The maximum number of cliques in dense g

The maximum number of cliques in dense graphs

✍ Bruce Hedman 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 372 KB

Denote the number of vertices of G by ]G[. A clique of graph G is a maximal complete subgraph. The density oJ(G) is the number of vertices in the largest clique of G. If ¢o(G)>~½ ]GI, then G has at most 2 t°l-'cG) cliques. The extremal graphs are then examined as wen. ## Terminology We will be co

An NC algorithm for the clique cover pro

An NC algorithm for the clique cover problem in cocomparability graphs and its application

✍ Chongkye Rhee; Y.Daniel Liang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 322 KB

The maximum number of q-cliques in a gra

The maximum number of q-cliques in a graph with no p-clique

✍ Steven Roman 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 805 KB

The complexity of the matching-cut probl

The complexity of the matching-cut problem for planar graphs and other graph classes

✍ Paul Bonsma 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB

## Abstract The Matching‐Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be ${\cal{NP}}$‐complete when restricted to graphs with maximum deg

An upper bound on the number of cliques

An upper bound on the number of cliques in a graph

✍ Martin Farber; Mihály Hujter; Zsolt Tuza 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 1 views