Kernelization and Complexity Results for Connectivity Augmentation Problems

DOI10.1007/978-3-540-73951-7_42MaRDI QIDQ3603551zbMATH OpenOpenAlexFDO

Authors Jiong Guo, Johannes Uhlmann

Publication date 17 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73951-7_42

Mathematics Subject Classification ID

Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Kernelization and complexity results for connectivity augmentation problems
• Parameterized algorithms to preserve connectivity
• Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
• Connectivity augmentation of graphs
• Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation

Cited in

(8)

• Two edge modification problems without polynomial kernels
• Kernelization and complexity results for connectivity augmentation problems
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• Two edge modification problems without polynomial kernels
• scientific article; zbMATH DE number 6857816 (Why is no real title available?)
• Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
• scientific article; zbMATH DE number 7720021 (Why is no real title available?)
• Two fixed-parameter algorithms for vertex covering by paths on trees

This page was built for publication: Kernelization and Complexity Results for Connectivity Augmentation Problems

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