Parameterized Complexity of Safe Set
From MaRDI portal
Publication:5119377
DOI10.7155/jgaa.00528zbMath1447.05200OpenAlexW3019773202MaRDI QIDQ5119377
Michael Lampis, Rémy Belmonte, Tesshu Hanaka, Yota Otachi, Ioannis Katsikarelis, Hirotaka Ono
Publication date: 4 September 2020
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.7155/jgaa.00528
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)
Related Items (4)
Constructive-destructive heuristics for the safe set problem ⋮ Models and algorithms for the weighted safe set problem ⋮ A combinatorial branch and bound for the safe set problem ⋮ On the connected safe number of some classes of graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Safe set problem on graphs
- On the computational complexity of vertex integrity and component order connectivity
- On problems without polynomial kernels
- An application of simultaneous diophantine approximation in combinatorial optimization
- Modular decomposition and transitive orientation
- Measuring the vulnerability for classes of intersection graphs
- Safe sets in graphs: graph classes and structural parameters
- Safe number and integrity of graphs
- Algorithmic meta-theorems for restrictions of treewidth
- The complexity of first-order and monadic second-order logic revisited
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Upper bounds to the clique width of graphs
- Approximating connected safe sets in weighted trees
- Partitioning a graph into small pieces with applications to path transversal
- The \(k\)-separator problem: polyhedra, complexity and approximation results
- On the weighted safe set problem on paths and cycles
- Approximating clique-width and branch-width
- Integer Programming with a Fixed Number of Variables
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Graph Layout Problems Parameterized by Vertex Cover
- Minkowski's Convex Body Theorem and Integer Programming
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Kernelization Lower Bounds Through Colors and IDs
- Approximating rank-width and clique-width quickly
- Safe sets, network majority on weighted trees
- Vulnerability parameters of split graphs
- Parameterized Algorithms
- Finding Branch-Decompositions and Rank-Decompositions
- Parameterized algorithms for generalizations of directed feedback vertex set
This page was built for publication: Parameterized Complexity of Safe Set
