Parameterized complexity of critical node cuts
From MaRDI portal
Publication:517024
DOI10.1016/j.tcs.2016.08.018zbMath1359.68135OpenAlexW1621893734MaRDI QIDQ517024
Barak Navon, Danny Hermelin, Moshe Kaspi, Christian Komusiewicz
Publication date: 16 March 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.08.018
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (3)
On critical node problems with vulnerable vertices ⋮ The critical node detection problem in networks: a survey ⋮ A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- A derandomized approximation algorithm for the critical node detection problem
- FPT algorithms for path-transversal and cycle-transversal problems
- Complexity of the critical node problem over trees
- Advice classes of parametrized tractability
- On the computational complexity of vertex integrity and component order connectivity
- Parameterized graph separation problems
- Simple and improved parameterized algorithms for multiterminal cuts
- On the parameterized complexity of multiple-interval graph problems
- Detecting critical nodes in sparse graphs
- On problems without polynomial kernels
- Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
- How the science of complex networks can help developing strategies against terrorism
- An improved parameterized algorithm for the minimum node multiway cut problem
- Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
- An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
- On Multiway Cut Parameterized above Lower Bounds
- Finding small separators in linear time via treewidth reduction
- Easy problems for tree-decomposable graphs
- New Limits to Classical and Quantum Instance Compression
- Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth
- Kernelization Lower Bounds by Cross-Composition
- Multicut is FPT
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
This page was built for publication: Parameterized complexity of critical node cuts
