2013/04/24 by Dániel Marx, Marx, Dániel, László A. Végh +1
Computer Science · Materials Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graphene research and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1304.6593
openalex publication_date 2013/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider connectivity-augmentation problems in a setting where each\npotential new edge has a nonnegative cost associated with it, and the task is\nto achieve a certain connectivity target with at most p new edges of minimum\ntotal cost. The main result is that the minimum cost augmentation of\nedge-connectivity from k-1 to k with at most p new edges is fixed-parameter\ntractable parameterized by p and admits a polynomial kernel. We also prove the\nfixed-parameter tractability of increasing edge-connectivity from 0 to 2, and\nincreasing node-connectivity from 1 to 2.\n