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

DOI10.1016/0020-0190(95)00027-AzbMath0875.68458OpenAlexW2033023054MaRDI QIDQ672487

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)

Related Items (11)

On computing the Galois lattice of bipartite distance hereditary graphs ⋮ Biclique comparability digraphs of bipartite graphs and minimum ranks of partial matrices ⋮ Unnamed Item ⋮ Recognizing interval digraphs and interval bigraphs in polynomial time ⋮ Partially ordered knapsack and applications to scheduling ⋮ Finding clubs in graph classes ⋮ Enumerating minimal dominating sets in chordal bipartite graphs ⋮ Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs ⋮ Finding maximum edge bicliques in convex bipartite graphs ⋮ On the generation of bicliques of a graph ⋮ Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs

Cites Work

• Characterizations of strongly chordal graphs
• Recognition of perfect elimination bipartite graphs
• Doubly lexical ordering of dense 0--1 matrices
• Characterizations of totally balanced matrices
• Arboricity and Subgraph Listing Algorithms
• Totally-Balanced and Greedy Matrices
• Doubly Lexical Orderings of Matrices
• Three Partition Refinement Algorithms
• Unnamed Item
• Unnamed Item

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