Geodesic
A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 2, pp. 389-396.

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

Circle graphs have applications to RNA bioinformatics, computational chemistry, and VLSI design. Additionally, many problems that are intractable on general graphs are efficient for circle graphs. This has driven research into algorithms for circle graphs. One well known graph problem is to find a maximum induced matching. This is NP-Hard, even for bipartite graphs. No algorithm for this problem that works directly on circle graphs has been proposed. However, since circle graphs are included in interval filament graphs, algorithms for this class can be applied to circle graphs. Unfortunately, this entails a large computational cost of $O(|V|^6)$ time. We propose an algorithm that operates directly on circle graphs, and requires only $O(|V|^3)$ time.
DOI : 10.7155/jgaa.00476
Keywords: circle graph, maximum induced matching, strong matching, dynamic programming 
@article{JGAA_2018_22_2_a9,
     author = {Max Ward and Andrew Gozzard and Michael Wise and Amitava Datta},
     title = {A {Faster} {Algorithm} for {Maximum} {Induced} {Matchings} on {Circle} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {389--396},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2018},
     doi = {10.7155/jgaa.00476},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00476/}
}
TY  - JOUR
AU  - Max Ward
AU  - Andrew Gozzard
AU  - Michael Wise
AU  - Amitava Datta
TI  - A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2018
SP  - 389
EP  - 396
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00476/
DO  - 10.7155/jgaa.00476
LA  - en
ID  - JGAA_2018_22_2_a9
ER  - 
%0 Journal Article
%A Max Ward
%A Andrew Gozzard
%A Michael Wise
%A Amitava Datta
%T A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
%J Journal of Graph Algorithms and Applications
%D 2018
%P 389-396
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00476/
%R 10.7155/jgaa.00476
%G en
%F JGAA_2018_22_2_a9
Max Ward; Andrew Gozzard; Michael Wise; Amitava Datta. A Faster Algorithm for Maximum Induced Matchings on Circle Graphs. Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 2, pp. 389-396. doi : 10.7155/jgaa.00476. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00476/

Cité par Sources :