Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits

DOI10.1016/0020-0190(95)00145-3zbMath0875.68698OpenAlexW2001053859MaRDI QIDQ1350298

Y. Daniel Liang, Norbert Blum

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00145-3

zbMATH Keywords

AlgorithmsHamiltonian circuitCircular convex bipartite graphConvex bipartite graphMaximum matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (16)

Cyclability in graph classes ⋮ Domination in some subclasses of bipartite graphs ⋮ Circular convex bipartite graphs: feedback vertex sets ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Induced Matching in Some Subclasses of Bipartite Graphs ⋮ Maximum Edge Bicliques in Tree Convex Bipartite Graphs ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Maximum weight induced matching in some subclasses of bipartite graphs ⋮ Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs ⋮ Dominating induced matching in some subclasses of bipartite graphs ⋮ Mutual exclusion scheduling with interval graphs or related classes. I ⋮ Circular Convex Bipartite Graphs: Feedback Vertex Set ⋮ Computing maximum non-crossing matching in convex bipartite graphs ⋮ Optimal point movement for covering circular regions ⋮ Tractable connected domination for restricted bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• TWO THEOREMS IN GRAPH THEORY
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• Efficiency of a Good But Not Linear Set Union Algorithm
• Paths, Trees, and Flowers
• Maximum matching in a convex bipartite graph
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits