No label defined (Q3347925)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3891419
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3891419 |
Statements
1984
0 references
Circle graphs
0 references
circular-arc graphs
0 references
maximum weight cliques
0 references
algorithms
0 references
0.9551891088485718
0 references
0.9197197556495668
0 references
0.9049686193466188
0 references
0.8981063365936279
0 references
0.8970168828964233
0 references
[For the entire collection see Zbl 0546.00007.] Circle graphs and circular-arc graphs are the intersection graphs of chords and arcs in a circle. In this paper the author presents algorithms for finding maximum weight cliques in these graphs assuming that their respective interval and arc representations are given. The running times of the algorithms are \(O(n^ 2\log n)\) for circle graphs and \(O(n^ 3)\) for circular-arc graphs, what improves the best known algorithms of \(O(n^ 3)\) and \(O(n^ 4)\), respectively, due to \textit{F. Gavril} [Networks 3, 261-273 (1973; Zbl 0259.05125) and ibid. 4, 357-369 (1974; Zbl 0309.05126)].
0 references