Structured Connectivity Augmentation

DOI10.1137/17M1146233zbMath1400.05134arXiv1706.04255WikidataQ128944013 ScholiaQ128944013MaRDI QIDQ4555048

Fedor V. Fomin, Dimitrios M. Thilikos, Petr A. Golovach

Publication date: 19 November 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

complexityconnectivity augmentationgraph superposition

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (1)

A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Edge-connectivity augmentation problems
• Minimum block containing a given graph
• Independence free graphs and vertex connectivity augmentation
• A note on finding the bridges of a graph
• On the optimal vertex-connectivity augmentation
• Algorithmic Aspects of Graph Connectivity
• Approximation Algorithms for Several Graph Augmentation Problems
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Augmentation Problems
• Detachments Preserving Local Edge-Connectivity of Graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• An exact characterization of tractable demand patterns for maximum disjoint path problems
• Parameterized Algorithms

This page was built for publication: Structured Connectivity Augmentation