On the fixed-parameter tractability of the maximum connectivity improvement problem

DOI10.1007/s00224-020-09977-6zbMath1453.68130arXiv1904.12000OpenAlexW3015556313MaRDI QIDQ2195571

Gianlorenzo D'Angelo, Federico Corò, Vahan V. Mkrtchyan

Publication date: 26 August 2020

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

connectivitygraph augmentationparameterized complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the approximability of the link building problem
• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• Path-contractions, edge deletions and connectivity preservation
• The parametric complexity of graph diameter augmentation
• Approximating Minimum-Cost $k$-Node Connected Subgraphs via Independence-Free Graphs
• Minimizing the Diameter of a Network Using Shortcut Edges
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• Augmentation Problems
• Improving the Betweenness Centrality of a Node by Adding Links
• Directed multicut is W[1-hard, even for four terminal pairs]
• Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
• The Parameterized Complexity of Centrality Improvement in Networks
• Parameterized Algorithms to Preserve Connectivity
• The Effect of New Links on Google Pagerank
• Steiner Forest Orientation Problems
• On the maximum connectivity improvement problem

This page was built for publication: On the fixed-parameter tractability of the maximum connectivity improvement problem