Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity

DOI10.1016/j.ipl.2007.11.020zbMath1186.68141OpenAlexW2002946373MaRDI QIDQ963381

Orestis A. Telelis, Vassilios Zissimopoulos

Publication date: 19 April 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.11.020

zbMATH Keywords

data structuresgraph connectivitydynamic graph algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Cites Work

• Maintaining bridge-connected and biconnected components on-line
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• The Min-Max Spanning Tree Problem and some extensions
• Maintaining the classes of 4-edge-connectivity in a graph on-line
• A linear time algorithm for the bottleneck biconnected spanning subgraph problem
• Algorithms for two bottleneck optimization problems
• A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
• A randomized linear-time algorithm to find minimum spanning trees
• Sparsification—a technique for speeding up dynamic graph algorithms
• Maintenance of 2- and 3-Edge-Connected Components of Graphs II
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Unnamed Item
• Unnamed Item

This page was built for publication: Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity