Parallel Complexity of the Connected Subgraph Problem

DOI10.1137/0222039MaRDI QIDQ4202213zbMATH OpenOpenAlexFDO

Authors L. M. Kirousis, Maria Serna, P. 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

\(P\)-complete problemsconnected subgraphconnectivityNC algorithm

Mathematics Subject Classification ID

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

Recommendations

• Parallel algorithms for connectivity problems in graph theory
• scientific article; zbMATH DE number 3930349
• The parallel complexity of approximating the high degree subgraph problem
• Parallel algorithms for finding connected components of a graph
• The parallel complexity of approximating the High Degree Subgraph problem
• scientific article; zbMATH DE number 1057772
• The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
• Parameterized complexity of connected even/odd subgraph problems
• Parameterized complexity of connected even/odd subgraph problems
• Parallel algorithms for connectivity problems on interval graphs

Cited in

(18)

• Parallel complexity of computing a maximal set of disjoint paths
• The parallel complexity of approximating the high degree subgraph problem
• Community detection using local neighborhood in complex networks
• Parallel approximation schemes for problems on planar graphs
• Sequential and parallel solution-biased search for subgraph algorithms
• Parameterized algorithms for min-max multiway cut and list digraph homomorphism
• Finding maximum subgraphs with relatively large vertex connectivity
• The VC-dimension of graphs with respect to k-connected subgraphs
• On counting and approximation variants of the subgraph connecting problem
• A glimpse at Paul G. Spirakis
• Parameterized complexity of connected even/odd subgraph problems
• scientific article; zbMATH DE number 1104333 (Why is no real title available?)
• scientific article; zbMATH DE number 1555967 (Why is no real title available?)
• The complexity of approximating \(\mathrm{PSPACE}\)-complete problems for hierarchical specifications
• scientific article; zbMATH DE number 2170471 (Why is no real title available?)
• Routing Problems on the Mesh of Buses
• On robust clusters of minimum cardinality in networks
• NC algorithms for partitioning sparse graphs into induced forests with an application

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

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