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

DOI10.1134/S0032946011030057zbMATH Open1236.05063MaRDI QIDQ764406FDOQ764406

Maxim Babenko, T. A. Urbanovich

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)

Cites Work

• Title not available (Why is that?)
• 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 log2 n) Time
• Regular subgraphs of almost regular graphs

Recommendations

• Title not available (Why is that?) 👍 👎
• A Linear-Time Algorithm for Finding a Maximal Planar Subgraph 👍 👎
• A linear time algorithm for finding maximal planar subgraphs 👍 👎
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph 👍 👎
• Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems 👍 👎
• Linear algorithm for domatic number problem on interval graphs 👍 👎
• A Linear Time Algorithm for Determining Almost Bipartite Graphs 👍 👎
• Computing Minimal Spanning Subgraphs in Linear Time 👍 👎
• A linear algorithm for the maximal planar subgraph problem 👍 👎
• On linear algebraic algorithms for the subgraph matching problem and its variants 👍 👎

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)