An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk

DOI10.1137/0204034MaRDI QIDQ4068762zbMATH OpenOpenAlexFDO

Authors Shimon Even

Publication date 1975

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://hdl.handle.net/1813/6027

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (05C99) Algorithms in computer science (68W99) Deterministic network models in operations research (90B10)

Cited in

(19)

• Acyclic k-connected subgraphs for distributed alternate routing in communications networks
• Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity
• On orienting graphs for connectivity: Projective planes and Halin graphs
• Game connectivity of graphs
• Tree-core and tree-coritivity of graphs
• An O(n+m) certifying triconnnectivity algorithm for Hamiltonian graphs
• Partition-based logical reasoning for first-order and propositional theories
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• Finding 2-edge and 2-vertex strongly connected components in quadratic time
• Finding triconnected components of graphs
• A simple variant of node connectivity is NP-complete
• Approximating minimum cuts under insertions
• Certifying algorithms
• Finding a small vertex cut on distributed networks
• Finding most-shattering minimum vertex cuts of polylogarithmic size in near-linear time
• Vertex connectivity in poly-logarithmic max-flows
• Improved algorithms for graph four-connectivity
• Approximation algorithms for treewidth
• Graph connectivity, partial words, and a theorem of Fine and Wilf

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk

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