Fast separation in a graph with an excluded minor

MaRDI QIDQ3576658zbMATH OpenFDO

Authors David R. Wood, Bruce Reed

Publication date 30 July 2010

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAE0110/0.html

zbMATH Keywords

graph algorithmminorseparator

Mathematics Subject Classification ID

Connectivity (05C40) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• A linear-time algorithm to find a separator in a graph excluding a minor
• Faster separators for shallow minor-free graphs via dynamic approximate distance oracles
• A Separator Theorem for Nonplanar Graphs
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Approximating small balanced vertex separators in almost linear time

Cited in

(13)

• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• A linear-time algorithm to find a separator in a graph excluding a minor
• A Reduction of the Anticoloring Problem to Connected Graphs
• Faster separators for shallow minor-free graphs via dynamic approximate distance oracles
• A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
• Optimization and Recognition for K 5-minor Free Graphs in Linear Time
• Edge separators for graphs excluding a minor
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Good r-divisions imply optimal amortized decremental biconnectivity
• Efficient enumeration of cliques in graphs with bounded maximum degree
• Quickly deciding minor-closed parameters in general graphs
• Single source shortest paths in H-minor free graphs
• On the maximum number of cliques in a graph

This page was built for publication: Fast separation in a graph with an excluded minor

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