A faster algorithm for maximum independent set on interval filament graphs

DOI10.7155/jgaa.00588zbMath1489.05137arXiv2110.04933OpenAlexW3205514659MaRDI QIDQ5084714

Max Ward, Darcy Best

Publication date: 28 June 2022

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

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

Mathematics Subject Classification ID

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

Cites Work

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

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