Safe Sets in Graphs: Graph Classes and Structural Parameters

DOI10.1007/978-3-319-48749-6_18zbMath1483.68245OpenAlexW2797680869MaRDI QIDQ2958317

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

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

graph algorithmtreewidthinterval graphfixed-parameter tractabilitysafe set

Mathematics Subject Classification ID

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

Related Items (1)

A new formulation for the safe set problem on graphs

Cites Work

• Safe set problem on graphs
• Sparsity. Graphs, structures, and algorithms
• Network majority on tree topological network
• 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
• Rankings of Graphs
• 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