A new approach on locally checkable problems
DOI10.1016/j.dam.2022.01.019zbMath1486.05293arXiv2006.00681OpenAlexW3114856694MaRDI QIDQ2127611
Carolina Lucía Gonzalez, Flavia Bonomo-Braberman
Publication date: 20 April 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2006.00681
treewidthGrundy domination\( [ k \)-Roman domination]local condition composition problemlocally checkable problemvertex partitioning problem
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (1)
Cites Work
- Total dominating sequences in graphs
- Double Roman domination
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Monadic second-order evaluations on tree-decomposable graphs
- \(k\)-tuple total domination in graphs
- Dominating sequences in graphs
- Perfect double Roman domination of trees
- Graph minors. III. Planar tree-width
- Rainbow domination on trees
- Complexity of the packing coloring problem for trees
- Limited packings in graphs
- Lucky labelings of graphs
- Relations between packing and covering numbers of a tree
- S-functions for graphs
- All structured programs have small tree width and good register allocation
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth. Computations and approximations
- Independence and average distance in graphs
- Roman domination in graphs.
- Distance-two labelings of graphs
- The complexity of first-order and monadic second-order logic revisited
- On the lucky choice number of graphs
- Maximal double Roman domination in graphs
- Outer independent double Roman domination
- Independent double Roman domination in graphs
- On the double Roman domination in graphs
- The minimum chromatic violation problem: a polyhedral study
- Distance-\(d\) independent set problems for bipartite and chordal graphs
- Nonserial dynamic programming
- Triple Roman domination in graphs
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Complexity of Total {k}-Domination and Related Problems
- $$\{k\}$$-Packing Functions of Graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Total domination in graphs
- Edge Dominating Sets in Graphs
- Labelling Graphs with a Condition at Distance 2
- Graph Classes: A Survey
- The $L(2,1)$-Labeling Problem on Graphs
- Reducibility among Combinatorial Problems
- Paths, Trees, and Flowers
- The Parameterized Complexity of Domination-Type Problems and Application to Linear Codes
- On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
- Acyclic colorings of planar graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A new approach on locally checkable problems
