Safe sets and in-dominating sets in digraphs

DOI10.1016/J.DAM.2023.12.012MaRDI QIDQ6153473zbMATH OpenOpenAlexFDO

Authors Yandong Bai, Jørgen Bang-Jensen, Shinya Fujita, Hirotaka Ono, A. Yeo

Publication date 14 February 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2023.12.012

zbMATH Keywords

NP-completepolynomial algorithmtournamentsafe setin-dominating set

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• Safe sets in graphs: graph classes and structural parameters
• Safe sets in graphs: graph classes and structural parameters
• Safe set problem on graphs
• Parameterized complexity of safe set
• Partitioning vertices into in- and out-dominating sets in digraphs

Cites work

• scientific article; zbMATH DE number 3914352 (Why is no real title available?)
• scientific article; zbMATH DE number 1256762 (Why is no real title available?)
• scientific article; zbMATH DE number 6986946 (Why is no real title available?)
• scientific article; zbMATH DE number 219267 (Why is no real title available?)
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• A combinatorial branch and bound for the safe set problem
• A compact mixed integer linear formulation for safe set problems
• Analytical approach to parallel repetition
• Approximating connected safe sets in weighted trees
• Complementary cycles of all lengths in tournaments
• Constructive-destructive heuristics for the safe set problem
• Digraph width measures in parameterized algorithmics
• Finding a dominating set on bipartite graphs
• Gallai colorings and domination in multipartite digraphs
• Improved Parameterized Upper Bounds for Vertex Cover
• Introduction to algorithms.
• On pancyclic digraphs
• On the weighted safe set problem on paths and cycles
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Reducibility among combinatorial problems
• Safe number and integrity of graphs
• Safe set problem on graphs
• Safe sets in graphs: graph classes and structural parameters
• Safe sets, network majority on weighted trees

This page was built for publication: Safe sets and in-dominating sets in digraphs

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