Finding a maximum matching in a circular-arc graph

DOI10.1016/0020-0190(93)90117-RzbMath0768.68159OpenAlexW2144795927MaRDI QIDQ1209984

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

algorithmmaximum matchinginterval graphscircular-arc graph

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)

Related Items (9)

Finding a maximum matching in a permutation graph ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ Matching and multidimensional matching in chordal and strongly chordal graphs ⋮ The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond ⋮ Unnamed Item ⋮ Efficient maximum matching algorithms for trapezoid graphs ⋮ Maximum matching in almost linear time on graphs of bounded clique-width ⋮ Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases

Cites Work

• TWO THEOREMS IN GRAPH THEORY
• Paths, Trees, and Flowers
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Unnamed Item

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