Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity
From MaRDI portal
Publication:1343167
DOI10.1007/BF01302965zbMath0810.05048OpenAlexW1510700297MaRDI QIDQ1343167
Publication date: 1 February 1995
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01302965
embeddingdigraphMonte Carlo algorithmconvex hullconnectivitydirected graphparallel algorithmLas Vegas algorithm
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Connectivity (05C40) Distributed algorithms (68W15)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- Matching is as easy as matrix inversion
- Constructing a perfect matching is in random NC
- The multi-tree approach to reliability in distributed networks
- Rubber bands, convex embeddings and graph connectivity
- A probabilistic algorithm for vertex connectivity of graphs
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Improved processor bounds for combinatorial problems in RNC
- Orthogonal representations and connectivity of graphs
- Connectivity in digraphs
- Three tree-paths
- Vertex-disjoint paths and edge-disjoint branchings in directed graphs
- Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
- Finding the Vertex Connectivity of Graphs
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
- An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
