Safe sets in graphs: graph classes and structural parameters

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

zbMATH Keywords

graph algorithmparameterized complexitysafe setgraph class

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

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