scientific article; zbMATH DE number 2086689

MaRDI QIDQ4737226zbMATH OpenFDO

Authors Ryuhei Uehara

Publication date 11 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2380/23800993.htm

zbMATH Keywords

Chordal bipartite graphsdesign and analysis of algorithmslexicographic breadth first searchstrongly chordal graphsvertex elimination ordering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
• Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
• Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Construction of a simple elimination scheme for a chordal comparability graph in linear time

Cited in

(23)

• From a simple elimination ordering to a strong elimination ordering in linear time
• Chordal bipartite graphs and crowns
• A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
• Construction of a simple elimination scheme for a chordal comparability graph in linear time
• Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
• On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Efficient parallel algorithm to compute a doubly perfect elimination ordering of a doubly chordal graph
• Improved algorithms for weakly chordal graphs
• Doubly Lexical Orderings of Matrices
• Satisfiability of acyclic and almost acyclic CNF formulas
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• scientific article; zbMATH DE number 1234609 (Why is no real title available?)
• \(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs
• Recognition and combinatorial optimization algorithms for bipartite chain graphs
• The cyclic rank completion problem with general blocks
• scientific article; zbMATH DE number 7250384 (Why is no real title available?)
• scientific article; zbMATH DE number 7651152 (Why is no real title available?)
• Graph classes and the switch Markov chain for matchings
• Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
• Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
• Hop domination in chordal bipartite graphs
• Enumerating minimal dominating sets and variants in chordal bipartite graphs

This page was built for publication:

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