Linear algorithm for selecting an almost regular spanning subgraph in an almost regular graph

DOI10.1134/S0032946011030057MaRDI QIDQ764406zbMATH OpenFDO

Authors T. A. Urbanovich, Maxim Babenko

Publication date 13 March 2012

Published in Problems of Information Transmission (Search for Journal in Brave)

zbMATH Keywords

almost \(d\)-regular graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Recommendations

• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A linear algorithm for the maximal planar subgraph problem
• On linear algebraic algorithms for the subgraph matching problem and its variants
• A linear time algorithm for determining almost bipartite graphs
• Linear time approximation algorithms for~degree~constrained subgraph problems
• A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
• A linear time algorithm for finding maximal planar subgraphs
• scientific article; zbMATH DE number 742959
• Computing Minimal Spanning Subgraphs in Linear Time
• Linear algorithm for domatic number problem on interval graphs

Cites work

• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Perfect matching for biconnected cubic graphs in \(O(n \log ^{2} n)\) time
• Regular subgraphs of almost regular graphs

This page was built for publication: Linear algorithm for selecting an almost regular spanning subgraph in an almost regular graph

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