Path-contractions, edge deletions and connectivity preservation

DOI10.4230/LIPICS.ESA.2017.47zbMATH Open1442.68074OpenAlexW2907306142MaRDI QIDQ5111736FDOQ5111736

Magnus Wahlström, M. S. Ramanujan, G. 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

Recommendations

• Path-contractions, edge deletions and connectivity preservation
• Parameterized algorithms to preserve connectivity
• Contracting graphs to paths and trees
• Contracting graphs to paths and trees
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges

zbMATH Keywords

connectivityvertex deletionstrong connectivityarc contraction

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Representative Sets and Irrelevant Vertices
• Parameterized Algorithms
• Title not available (Why is that?)
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• The minimum spanning strong subdigraph problem is fixed parameter tractable
• Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Minimal edge-coverings of pairs of sets
• Augmenting Undirected Node-Connectivity by One
• Edge-connectivity augmentation problems
• An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
• Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems
• Kernelization and complexity results for connectivity augmentation problems
• Parameterized Algorithms to Preserve Connectivity

Cited In (1)

• Maintaining shortest paths under deletions in weighted directed graphs

This page was built for publication: Path-contractions, edge deletions and connectivity preservation

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