Parallel Complexity of the Connected Subgraph Problem

DOI10.1137/0222039zbMath0773.68042OpenAlexW2021366964MaRDI QIDQ4202213

Lefteris M. Kirousis, Maria J. Serna, Paul G. Spirakis

Publication date: 1 September 1993

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

Full work available at URL: https://doi.org/10.1137/0222039

zbMATH Keywords

connectivityconnected subgraphNC algorithm\(P\)-complete problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Distributed algorithms (68W15)

Related Items (8)

Community detection using local neighborhood in complex networks ⋮ Finding maximum subgraphs with relatively large vertex connectivity ⋮ A Glimpse at Paul G. Spirakis ⋮ The VC-dimension of graphs with respect to \(k\)-connected subgraphs ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Parallel approximation schemes for problems on planar graphs ⋮ The complexity of approximating PSPACE-complete problems for hierarchical specifications ⋮ On robust clusters of minimum cardinality in networks

This page was built for publication: Parallel Complexity of the Connected Subgraph Problem