Finding a maximum matching in a circular-arc graph

DOI10.1016/0020-0190(93)90117-RMaRDI QIDQ1209984zbMATH OpenOpenAlexFDO

Authors Y. Daniel Liang, Chongkye Rhee

Publication date 16 May 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90117-r

zbMATH Keywords

algorithminterval graphscircular-arc graphmaximum matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Finding maximum cliques on circular-arc graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
• Stability in circular arc graphs
• An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs

Cites work

• scientific article; zbMATH DE number 3965452 (Why is no real title available?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Paths, Trees, and Flowers
• TWO THEOREMS IN GRAPH THEORY

Cited in

(11)

• The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
• Stability in circular arc graphs
• The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
• Finding a maximum matching in a permutation graph
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
• Maximum matching in almost linear time on graphs of bounded clique-width
• Finding maximum matchings in RDV graphs efficiently
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• On adaptive algorithms for maximum matching
• Efficient maximum matching algorithms for trapezoid graphs

This page was built for publication: Finding a maximum matching in a circular-arc graph

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