Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs

DOI10.1007/BFB0009490MaRDI QIDQ6487434zbMATH OpenFDO

Authors Maw-Shang Chang

Publication date 25 January 2023

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorics of partially ordered sets (06A07)

Recommendations

• Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
• scientific article; zbMATH DE number 2086689
• Connected matchings in chordal bipartite graphs
• Algorithmic aspects of bipartite graphs
• Maximum induced matchings for chordal graphs in linear time

Cites work

• scientific article; zbMATH DE number 3896983 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• Algorithms for maximumk-colorings andk-coverings of transitive graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Bipartite permutation graphs
• Characterizations of strongly chordal graphs
• Classes of bipartite graphs related to chordal graphs
• Computing the Minimum Fill-In is NP-Complete
• Decomposition by clique separators
• Doubly lexical ordering of dense 0--1 matrices
• Triangulated graphs and the elimination process

Cited in

(23)

• scientific article; zbMATH DE number 5059933 (Why is no real title available?)
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
• Connected matchings in chordal bipartite graphs
• The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
• \(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs
• On some graphs with a unique perfect matching
• Solving the all-pairs-shortest-length problem on chordal bipartite graphs
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Uniformly monotone partitioning of polygons
• The power of linear-time data reduction for maximum matching
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Maximum matching in almost linear time on graphs of bounded clique-width
• The Power of Linear-Time Data Reduction for Maximum Matching
• scientific article; zbMATH DE number 7561360 (Why is no real title available?)
• On the minimum chordal completion polytope
• Listing all potential maximal cliques of a graph
• scientific article; zbMATH DE number 6299967 (Why is no real title available?)
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• A revisit of the scheme for computing treewidth and minimum fill-in
• scientific article; zbMATH DE number 597814 (Why is no real title available?)
• scientific article; zbMATH DE number 2086689 (Why is no real title available?)
• On adaptive algorithms for maximum matching

This page was built for publication: Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs

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