Data structures for node connectivity queries

DOI10.4230/LIPICS.ESA.2022.82MaRDI QIDQ6969596zbMATH OpenFDO

Authors Zeev Nutov

Publication date 19 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2022.82

zbMATH Keywords

data structureminimum cutsnode connectivityconnectivity queries

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A note on labeling schemes for graph connectivity
• An O(k^3 n)-approximation algorithm for vertex-connectivity survivable network design
• An optimal labeling for node connectivity
• Approximating subset \(k\)-connectivity problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Dividing a Graph into Triconnected Components
• Ecken vom Grad n in minimalen n-fach zusammenhängenden Graphen
• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• Labeling Schemes for Flow and Connectivity
• Labeling schemes for vertex connectivity
• Multi-Terminal Network Flows
• On chromatic number of graphs and set-systems
• On element-connectivity preserving graph simplification
• Optimal vertex connectivity oracles
• Reinventing the wheel
• Smallest-last ordering and clustering and graph coloring algorithms

Cited in

(1)

• Space complexity of vertex connectivity oracles

This page was built for publication: Data structures for node connectivity queries

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