A Faster Algorithm for Maximum Induced Matchings on Circle Graphs

DOI10.7155/jgaa.00476zbMath1394.05126OpenAlexW2888579767WikidataQ129342643 ScholiaQ129342643MaRDI QIDQ4585063

Michael M. Wise, Andrew Gozzard, Amitava Datta, Max Ward

Publication date: 6 September 2018

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

Full work available at URL: https://doi.org/10.7155/jgaa.00476

zbMATH Keywords

maximum induced matching

Mathematics Subject Classification ID

Applications of graph theory (05C90) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A faster algorithm for maximum independent set on interval filament graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets and cliques in intersection graphs of filaments
• An algorithm for the maximum weight independent set problem on outerstring graphs
• An output sensitive algorithm for computing a maximum independent set of a circle graph
• Minimum weight feedback vertex sets in circle graphs
• New clique and independent set algorithms for circle graphs
• Induced matchings
• Induced matchings in intersection graphs.
• Counting hexagonal patches and independent sets in circle graphs
• A Maximum Weight Clique Algorithm For Dense Circle Graphs With Many Shared Endpoints
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• Finding maximum cliques in circle graphs
• Algorithms for Loop Matchings
• Efficient drawing of RNA secondary structure
• Algorithms for a maximum clique and a maximum independent set of a circle graph