Computing vertex-disjoint paths in large graphs using MAOs

DOI10.4230/LIPICS.ISAAC.2018.13MaRDI QIDQ5091003zbMATH OpenFDO

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

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2018.13

zbMATH Keywords

big datacertifyingcomputing disjoint pathslarge graphslinear-timemaximal adjacency orderingmaximum cardinality searchvertex-connectivity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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

Cites work

• A correctness certificate for the Stoer-Wagner min-cut algorithm
• A simple min-cut algorithm
• A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
• Algorithmic Aspects of Graph Connectivity
• Certifying algorithms
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• 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
• Finding the Vertex Connectivity of Graphs
• Grad und lokaler Zusammenhang in endlichen Graphen
• Graph theory
• Network Flow and Testing Graph Connectivity
• Rubber bands, convex embeddings and graph connectivity
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• 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)