Safe sets in graphs: graph classes and structural parameters
From MaRDI portal
Publication:1631677
DOI10.1007/s10878-017-0205-2zbMath1412.90156OpenAlexW4391578263MaRDI QIDQ1631677
Tadashi Sakuma, Raquel Águeda, Hirotaka Ono, Shinya Fujita, Yasuko Matsui, Yannis Manoussakis, Zsolt Tuza, Leandro Montero, Nathann Cohen, Sylvain Legay, Yota Otachi, Reza Naserasr, Renyu Xu
Publication date: 6 December 2018
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://hal.science/hal-01644491
Related Items (12)
Safe number and integrity of graphs ⋮ Approximating connected safe sets in weighted trees ⋮ Constructive-destructive heuristics for the safe set problem ⋮ On the weighted safe set problem on paths and cycles ⋮ Models and algorithms for the weighted safe set problem ⋮ Safe sets and in-dominating sets in digraphs ⋮ A combinatorial branch and bound for the safe set problem ⋮ Parameterized Complexity of Safe Set ⋮ Stable structure on safe set problems in vertex-weighted graphs ⋮ A compact mixed integer linear formulation for safe set problems ⋮ A new formulation for the safe set problem on graphs ⋮ On the connected safe number of some classes of graphs
Cites Work
- Safe set problem on graphs
- Sparsity. Graphs, structures, and algorithms
- Network majority on tree topological network
- On the hardness of approximating minimum vertex cover
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Treewidth. Computations and approximations
- Easy problems for tree-decomposable graphs
- Structural Parameterizations of the Mixed Chinese Postman Problem
- Graph Layout Problems Parameterized by Vertex Cover
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- On Linear Time Minor Tests with Depth-First Search
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Rankings of Graphs
- Reducibility among Combinatorial Problems
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: Safe sets in graphs: graph classes and structural parameters
