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

DOI10.1134/S0032946011030057zbMATH Open1236.05063MaRDI QIDQ764406FDOQ764406

Authors: T. A. Urbanovich, Maxim Babenko 

Publication date: 13 March 2012

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

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

zbMATH Keywords

almost \(d\)-regular graphs

Mathematics Subject Classification ID

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

Cites Work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• 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)