A linear time algorithm for determining almost bipartite graphs

DOI10.1007/978-3-319-17142-5_15MaRDI QIDQ2948463zbMATH OpenOpenAlexFDO

Authors Dayu He, Xin He

Publication date 30 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-17142-5_15

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2159644
• Planar graph bipartization in linear time
• Recognizing Graphs Close to Bipartite Graphs
• A linear time algorithm for graph partition problems
• Edge coloring nearly bipartite graphs

Cited in

(8)

• Simple linear time approximation algorithm for betweenness
• A linear time algorithm for the nullity of vertex-weighted block graphs
• A deterministic O(m m) time algorithm for the Reeb graph
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• scientific article; zbMATH DE number 5543290 (Why is no real title available?)
• scientific article; zbMATH DE number 1522753 (Why is no real title available?)
• scientific article; zbMATH DE number 1796979 (Why is no real title available?)
• Linear algorithm for selecting an almost regular spanning subgraph in an almost regular graph

This page was built for publication: A linear time algorithm for determining almost bipartite graphs

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