Path-contractions, edge deletions and connectivity preservation

DOI10.4230/LIPICS.ESA.2017.47MaRDI QIDQ5111736zbMATH OpenOpenAlexFDO

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

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

connectivityvertex deletionstrong connectivityarc contraction

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Augmenting undirected node-connectivity by one
• Connections in combinatorial optimization
• Edge-connectivity augmentation problems
• Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
• Kernelization and complexity results for connectivity augmentation problems
• Minimal edge-coverings of pairs of sets
• Parameterized algorithms
• Parameterized algorithms to preserve connectivity
• Recent developments in kernelization: a survey
• Representative sets and irrelevant vertices: new tools for kernelization
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• The minimum spanning strong subdigraph problem is fixed parameter tractable

Cited in

(2)

• Path-contractions, edge deletions and connectivity preservation
• 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)