Path-Contractions, Edge Deletions and Connectivity Preservation

DOI10.4230/LIPIcs.ESA.2017.47zbMath1442.68074OpenAlexW2907306142MaRDI QIDQ5111736

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

Publication date: 27 May 2020

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7827/pdf/LIPIcs-ESA-2017-47.pdf

zbMATH Keywords

connectivitystrong connectivityvertex deletionarc contraction

Mathematics Subject Classification ID

Connectivity (05C40) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Kernelization and complexity results for connectivity augmentation problems
• Augmenting Undirected Node-Connectivity by One
• Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Representative Sets and Irrelevant Vertices
• Parameterized Algorithms to Preserve Connectivity
• Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation
• Parameterized Algorithms
• An Algorithm for Finding a Minimum Equivalent Graph of a Digraph