๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Algorithms for a maximum clique and a maximum independent set of a circle graph

โœ Scribed by F. Gavril

Publisher
John Wiley and Sons
Year
1973
Tongue
English
Weight
523 KB
Volume
3
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis

Abstract

Consider a family of chords in a circle. A circle graph is obtained by representing each chord by a vertex, two vertices being connected by an edge when the corresponding chords intersect. In this paper, we describe efficient algorithms for finding a maximum clique and a maximum independent set of circle graphs. These algorithms require at most n^3^ steps, where n is the number of vertices in the graph.

๐Ÿ“œ SIMILAR VOLUMES

Maximum independent sets of circular-arc
Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs
โœ Zheng, S. Q. ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 421 KB ๐Ÿ‘ 2 views

We present a simple optimal algorithm for the problem of finding maximum independent sets of circular-arc graphs. Given an intersection model S of a circular-arc graph G , our algorithm computes a maximum independent set of G in O ( n ) space and O ( n ) or O(n log n ) time, depending on whether the

Hitting all maximum cliques with a stabl
Hitting all maximum cliques with a stable set using lopsided independent transversals
โœ Andrew D. King ๐Ÿ“‚ Article ๐Ÿ“… 2010 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 82 KB

Rabern recently proved that any graph with โ‰ฅ 3 4 ( +1) contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exists for any graph with > 2 3 ( +1). This is tight, i.e. the inequality in the statement must be strict. The proof relies on finding a