Safe sets in graphs: graph classes and structural parameters

DOI10.1007/978-3-319-48749-6_18MaRDI QIDQ2958317zbMATH OpenOpenAlexFDO

Authors Nathann Cohen, Shinya Fujita, Sylvain Legay, Leandro Montero, Reza Naserasr, Yota Otachi, Tadashi Sakuma, Zsolt Tuza, Renyu Xu, R. Águeda, Y. Manoussakis, Yasuko Matsui

Publication date 1 February 2017

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-48749-6_18

zbMATH Keywords

fixed-parameter tractabilitygraph algorithminterval graphsafe settreewidth

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Safe sets in graphs: graph classes and structural parameters
• Parameterized complexity of safe set
• Safe set problem on graphs
• Models and algorithms for the weighted safe set problem
• A new formulation for the safe set problem on graphs

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Easy problems for tree-decomposable graphs
• Graph Layout Problems Parameterized by Vertex Cover
• Network majority on tree topological network
• On Linear Time Minor Tests with Depth-First Search
• Parameterized algorithms
• Rankings of Graphs
• Safe set problem on graphs
• Sparsity. Graphs, structures, and algorithms
• Structural parameterizations of the mixed Chinese postman problem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Treewidth. Computations and approximations

Cited in

(12)

• Safe sets in graphs: graph classes and structural parameters
• On the connected safe number of some classes of graphs
• Safety in s-t paths, trails and walks
• A compact mixed integer linear formulation for safe set problems
• A new formulation for the safe set problem on graphs
• Parameterized complexity of safe set
• Safe set problem on graphs
• scientific article; zbMATH DE number 6986946 (Why is no real title available?)
• Parameterized complexity of safe set
• scientific article; zbMATH DE number 7746012 (Why is no real title available?)
• Safe sets and in-dominating sets in digraphs
• A combinatorial branch and bound for the safe set problem

This page was built for publication: Safe sets in graphs: graph classes and structural parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2958317)