Path-contractions, edge deletions and connectivity preservation

DOI10.1016/j.jcss.2018.10.001zbMath1412.68084arXiv1704.06622OpenAlexW2963841226WikidataQ128987347 ScholiaQ128987347MaRDI QIDQ1713475

Gregory Gutin, Felix Reidl, Magnus Wahlström, M. S. Ramanujan

Publication date: 25 January 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1704.06622

zbMATH Keywords

graph connectivityparameterized complexityvertex deletionpath contraction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40)

Related Items

On the fixed-parameter tractability of the maximum connectivity improvement problem, A survey of parameterized algorithms and the complexity of edge modification, Basic Terminology, Notation and Results

Cites Work

• Fixed-parameter tractability and completeness II: On completeness for W[1]
• The minimum spanning strong subdigraph problem is fixed parameter tractable
• Edge-connectivity augmentation problems
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Minimal edge-coverings of pairs of sets
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Kernelization and complexity results for connectivity augmentation problems
• Augmenting Undirected Node-Connectivity by One
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Easy problems for tree-decomposable graphs
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Network Flow and Testing Graph Connectivity
• Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
• Reducing CMSO model checking to highly connected graphs
• Parameterized Algorithms to Preserve Connectivity
• An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
• Unnamed Item
• Unnamed Item
• Unnamed Item