Computing vertex-disjoint paths in large graphs using MAOs

DOI10.4230/LIPICS.ISAAC.2018.13MaRDI QIDQ5091003FDOQ5091003

Authors: Johanna E. Preißer, Jens M. Schmidt 

Publication date: 21 July 2022

Recommendations

• Computing vertex-disjoint paths in large graphs using MAOs
• The Vertex-Disjoint Menger Problem in Planar Graphs
• scientific article; zbMATH DE number 437535
• scientific article; zbMATH DE number 3858436
• STACS 2004

zbMATH Keywords

big datavertex-connectivitylinear-timelarge graphsmaximum cardinality searchcomputing disjoint pathsmaximal adjacency orderingcertifying

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Graph theory
• Algorithmic Aspects of Graph Connectivity
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Network Flow and Testing Graph Connectivity
• Finding the Vertex Connectivity of Graphs
• A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
• A simple min-cut algorithm
• Certifying algorithms
• Rubber bands, convex embeddings and graph connectivity
• A correctness certificate for the Stoer-Wagner min-cut algorithm
• Contractions, removals, and certifying 3-connectivity in linear time
• Existenz gewisser Konfigurationen in \(n\)-gesättigten Graphen und in Graphen genügend großer Kantendichte
• Grad und lokaler Zusammenhang in endlichen Graphen
• Sparse connectivity certificates via MA orderings in graphs

This page was built for publication: Computing vertex-disjoint paths in large graphs using MAOs

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