Geodesic
A faster algorithm for maximum independent set on interval filament graphs
Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 1, pp. 199-205.

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

We provide an algorithm requiring only $O(N^2)$ time to compute the maximum weight independent set in an $N$-vertex interval filament graph. This implies an $O(N^4)$-time algorithm to compute the maximum weight induced matching in such graphs. Both algorithms significantly improve upon the previous best complexities for these problems. Previously, the maximum weight independent set and maximum weight induced matching problems required $O(N^3)$ and $O(N^6)$ time respectively. 
@article{JGAA_2022_26_1_a10,
     author = {Darcy Best and Max Ward},
     title = {A faster algorithm for maximum independent set on interval filament graphs},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {199--205},
     publisher = {mathdoc},
     volume = {26},
     number = {1},
     year = {2022},
     doi = {10.7155/jgaa.00588},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00588/}
}
TY  - JOUR
AU  - Darcy Best
AU  - Max Ward
TI  - A faster algorithm for maximum independent set on interval filament graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 199
EP  - 205
VL  - 26
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00588/
DO  - 10.7155/jgaa.00588
LA  - en
ID  - JGAA_2022_26_1_a10
ER  - 
%0 Journal Article
%A Darcy Best
%A Max Ward
%T A faster algorithm for maximum independent set on interval filament graphs
%J Journal of Graph Algorithms and Applications
%D 2022
%P 199-205
%V 26
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00588/
%R 10.7155/jgaa.00588
%G en
%F JGAA_2022_26_1_a10
Darcy Best; Max Ward. A faster algorithm for maximum independent set on interval filament graphs. Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 1, pp. 199-205. doi : 10.7155/jgaa.00588. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00588/

Cité par Sources :