Recognizing sparse perfect elimination bipartite graphs

DOI10.1007/978-3-642-20712-9_35MaRDI QIDQ3007647zbMATH OpenOpenAlexFDO

Authors Matthijs Bomhoff

Publication date 17 June 2011

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://research.utwente.nl/en/publications/recognizing-sparse-perfect-elimination-bipartite-graphs(86ee3910-9d47-4f07-afff-b8c517c2d70e).html

zbMATH Keywords

algorithmsbipartite graphsperfect eliminationsparse graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Computational methods for sparse matrices (65F50) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A note on perfect partial elimination
• A perfect matching algorithm for sparse bipartite graphs
• Bisimplicial edges in bipartite graphs
• Sparse Partial Pivoting in Time Proportional to Arithmetic Operations
• On the ordering of sparse linear systems

Cites work

• Algorithmic Aspects of Vertex Elimination on Directed Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Computing the Minimum Fill-In is NP-Complete
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1775386 (Why is no real title available?)
• Matrix multiplication via arithmetic progressions
• Perfect Elimination and Chordal Bipartite Graphs
• Recognition of perfect elimination bipartite graphs
• Recognizing quasi-triangulated graphs.
• Toward Characterization of Perfect Elimination Digraphs

Cited in

(1)

• Recognizing Perfect 2-Split Graphs

This page was built for publication: Recognizing sparse perfect elimination bipartite graphs

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