A faster algorithm for maximum independent set on interval filament graphs

DOI10.7155/JGAA.00588MaRDI QIDQ5084714zbMATH OpenOpenAlexFDO

Authors Max Ward, Darcy Best

Publication date 28 June 2022

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2110.04933

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: We provide an algorithm requiring only $O(N^2)$ time to compute the maximum weight independent set of interval filament graphs. This also implies an $O(N^4)$ algorithm to compute the maximum weight induced matching of interval filament 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.

Recommendations

• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• Independent sets of maximum weight in apple-free graphs
• Maximum weight independent sets and cliques in intersection graphs of filaments
• A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs

Cites work

• 3D-interval-filament graphs
• A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
• Algorithms and Computation
• Finding a Maximum Independent Set
• Induced matchings in intersection graphs.
• Maximum weight independent sets and cliques in intersection graphs of filaments
• On the induced matching problem

Cited in

(5)

• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Winning strategies for the synchronization game on subclasses of finite automata
• A new notion of regularity: finite state automata accepting graphs

This page was built for publication: A faster algorithm for maximum independent set on interval filament graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084714)