Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00588
A faster algorithm for maximum independent set on interval filament graphs
Vol. 26, no. 1, pp. 199-205, 2022. Concise paper.
Abstract 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.
 This work is licensed under the terms of the CC-BY license.
Submitted: October 2021.
Reviewed: January 2022.
Revised: March 2022.
Accepted: May 2022.
Final: June 2022.
Published: June 2022.
Communicated by Alexander Wolff
article (PDF)
BibTeX