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

connectivityconnected subgraphNC algorithm\(P\)-complete problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Connectivity (05C40) 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

(15)

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

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)