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

DOI10.1016/0020-0190(95)00027-AzbMATH Open0875.68458OpenAlexW2033023054MaRDI QIDQ672487FDOQ672487

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

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

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)

Cites Work

• Title not available (Why is that?)
• Doubly lexical ordering of dense 0--1 matrices
• Three Partition Refinement Algorithms
• Characterizations of strongly chordal graphs
• Characterizations of totally balanced matrices
• Arboricity and Subgraph Listing Algorithms
• Totally-Balanced and Greedy Matrices
• Doubly Lexical Orderings of Matrices
• Recognition of perfect elimination bipartite graphs
• Title not available (Why is that?)

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
• Problems and invariants connected with bicliques and multicliques of graphs
• Finding maximum edge bicliques in convex bipartite graphs
• Partially ordered knapsack and applications to scheduling
• On computing the Galois lattice of bipartite distance hereditary graphs
• Title not available (Why is that?)
• 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)