Algorithmic Aspects of Graph Connectivity
From MaRDI portal
Publication:3543582
DOI10.1017/CBO9780511721649zbMath1172.05003OpenAlexW2279278398MaRDI QIDQ3543582
Toshihide Ibaraki, Hiroshi Nagamochi
Publication date: 4 December 2008
Full work available at URL: https://doi.org/10.1017/cbo9780511721649
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (37)
Depth functions and mutidimensional medians on minimal spanning trees ⋮ Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts ⋮ Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time ⋮ Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs ⋮ On the robustness to multiple agent losses in 2D and 3D formations ⋮ Structured Connectivity Augmentation ⋮ Phase retrieval of complex and vector-valued functions ⋮ Minimum Cuts and Sparsification in Hypergraphs ⋮ Graph searches and their end vertices ⋮ Quantum graphs which optimize the spectral gap ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ Structured Connectivity Augmentation ⋮ A metric to compare vulnerability of the graphs of different sizes ⋮ Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Static and dynamic source locations in undirected networks ⋮ The firebreak problem ⋮ Minimum shared‐power edge cut ⋮ Characterizing redundant rigidity and redundant global rigidity of body-hinge graphs ⋮ Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs ⋮ The double-bubble problem on the square lattice ⋮ Unnamed Item ⋮ Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems ⋮ A simple certifying algorithm for 3-edge-connectivity ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions ⋮ Certifying 3-edge-connectivity ⋮ Approximating source location and star survivable network problems ⋮ In search of the densest subgraph ⋮ Unnamed Item ⋮ Computing vertex-disjoint paths in large graphs using MAOs ⋮ Fault-Tolerant Maximal Local-Connectivity on Cayley Graphs Generated by Transpositions ⋮ Symmetric submodular system: contractions and Gomory-Hu tree ⋮ Approximating Source Location and Star Survivable Network Problems ⋮ A new parameter for a broadcast algorithm with locally bounded Byzantine faults ⋮ On the complexity of isoperimetric problems on trees ⋮ Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs ⋮ An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure
This page was built for publication: Algorithmic Aspects of Graph Connectivity
