Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph

DOI10.1016/0020-0190(95)00027-AMaRDI QIDQ672487zbMATH OpenOpenAlexFDO

Authors Dieter Kratsch, Ton Kloks

Publication date 28 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)00027-a

zbMATH Keywords

Design of algorithmsChordal bipartite graphsEfficient algorithms

Mathematics Subject Classification ID

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

Recommendations

• Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
• scientific article; zbMATH DE number 2086689
• Algorithmic aspects of bipartite graphs
• Some aspects of the semi-perfect elimination

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 512817 (Why is no real title available?)
• Arboricity and Subgraph Listing Algorithms
• Characterizations of strongly chordal graphs
• Characterizations of totally balanced matrices
• Doubly Lexical Orderings of Matrices
• Doubly lexical ordering of dense 0--1 matrices
• Recognition of perfect elimination bipartite graphs
• Three Partition Refinement Algorithms
• Totally-Balanced and Greedy Matrices

Cited in

(16)

• Finding clubs in graph classes
• Generating and characterizing the perfect elimination orderings of a chordal graph
• Biclique comparability digraphs of bipartite graphs and minimum ranks of partial matrices
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
• Enumerating minimal dominating sets in chordal bipartite graphs
• On the generation of bicliques of a graph
• Treewidth of Chordal Bipartite Graphs
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
• Finding maximum edge bicliques in convex bipartite graphs
• Problems and invariants connected with bicliques and multicliques of graphs
• Partially ordered knapsack and applications to scheduling
• On computing the Galois lattice of bipartite distance hereditary graphs
• scientific article; zbMATH DE number 2086689 (Why is no real title available?)
• Chordal bipartite graphs and crowns

This page was built for publication: Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph

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