Geodesic
A Maximum Weight Clique Algorithm For Dense Circle Graphs With Many Shared Endpoints
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 547-554.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Circle graphs are derived from the intersections of a set of chords. They have applications in VLSI design, bioinformatics, and chemistry. Some intractable problems on general graphs can be solved in polynomial time on circle graphs. As such, the study of circle graph algorithms has received attention. State-of-the-art algorithms for finding the maximum weight clique of a circle graph are very efficient when the graph is sparse. However, these algorithms require $\Theta(n^2)$ time when the graph is dense. We present an algorithm that is a factor of $\sqrt{n}$ faster for dense graphs in which many chord endpoints are shared. We also argue that these assumptions are practical.
DOI : 10.7155/jgaa.00428
Keywords: circle graph, weighted, clique, shared endpoints, dynamic programming 
@article{JGAA_2017_21_4_a6,
     author = {Max Ward and Andrew Gozzard and Amitava Datta},
     title = {A {Maximum} {Weight} {Clique} {Algorithm} {For} {Dense} {Circle} {Graphs} {With} {Many} {Shared} {Endpoints}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {547--554},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2017},
     doi = {10.7155/jgaa.00428},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00428/}
}
TY  - JOUR
AU  - Max Ward
AU  - Andrew Gozzard
AU  - Amitava Datta
TI  - A Maximum Weight Clique Algorithm For Dense Circle Graphs With Many Shared Endpoints
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 547
EP  - 554
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00428/
DO  - 10.7155/jgaa.00428
LA  - en
ID  - JGAA_2017_21_4_a6
ER  - 
%0 Journal Article
%A Max Ward
%A Andrew Gozzard
%A Amitava Datta
%T A Maximum Weight Clique Algorithm For Dense Circle Graphs With Many Shared Endpoints
%J Journal of Graph Algorithms and Applications
%D 2017
%P 547-554
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00428/
%R 10.7155/jgaa.00428
%G en
%F JGAA_2017_21_4_a6
Max Ward; Andrew Gozzard; Amitava Datta. A Maximum Weight Clique Algorithm For Dense Circle Graphs With Many Shared Endpoints. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 547-554. doi : 10.7155/jgaa.00428. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00428/

Cité par Sources :