Secluded connectivity problems

DOI10.1007/s00453-016-0222-zzbMath1380.68307arXiv1212.6176OpenAlexW2559735673MaRDI QIDQ1679225

Shiri Chechik, Merav Parter, David Peleg, Matthew P. Johnson

Publication date: 9 November 2017

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items (9)

Parameterized complexity of secluded connectivity problems ⋮ Finding connected secluded subgraphs ⋮ Finding \(k\)-secluded trees faster ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Finding \(k\)-secluded trees faster ⋮ Detecting monomials with \(k\) distinct variables ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ On the computational complexity of length- and neighborhood-constrained path problems ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation and hardness results for label cut and related problems
• Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
• On the hardness of approximating label-cover
• The labeled perfect matching in bipartite graphs
• On the minimum label spanning tree problem
• The parameterized complexity of some minimum label problems
• Approximation algorithms and hardness results for labeled connectivity problems
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Improved Steiner Tree Algorithms for Bounded Treewidth
• A threshold of ln n for approximating set cover
• Graph minors. II. Algorithmic aspects of tree-width
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Reducibility among Combinatorial Problems
• A linear time algorithm for finding tree-decompositions of small treewidth
• Treewidth: Structure and Algorithms
• Secluded Path via Shortest Path

This page was built for publication: Secluded connectivity problems