Kernelization and complexity results for connectivity augmentation problems
From MaRDI portal
combinatorial problemdata reductionfixed-parameter (in)tractabilitygraph algorithmNP-complete problem
Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
- Kernelization and Complexity Results for Connectivity Augmentation Problems
- Parameterized algorithms to preserve connectivity
- Connectivity augmentation of graphs
- Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
- Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
Cites work
- A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- Approximation Algorithms for Graph Augmentation
- Approximation Algorithms for Several Graph Augmentation Problems
- Augmentation Problems
- Depth-First Search and Linear Graph Algorithms
- Exact Algorithms for Cluster Editing: Evaluation and Experiments
- Experiments on data reduction for optimal domination in networks
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Smallest Augmentations to Biconnect a Graph
Cited in
(10)- Path-contractions, edge deletions and connectivity preservation
- Augmenting weighted graphs to establish directed point-to-point connectivity
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Kernelization and Complexity Results for Connectivity Augmentation Problems
- scientific article; zbMATH DE number 6857816 (Why is no real title available?)
- Path-contractions, edge deletions and connectivity preservation
- Parameterized algorithms to preserve connectivity
- scientific article; zbMATH DE number 7720021 (Why is no real title available?)
- A survey of parameterized algorithms and the complexity of edge modification
- Parameterized algorithms for node connectivity augmentation problems
This page was built for publication: Kernelization and complexity results for connectivity augmentation problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057175)
