Parameterized complexity of graph burning

DOI10.1007/s00453-022-00962-8OpenAlexW3042241622MaRDI QIDQ2161013

Yasuaki Kobayashi, Yota Otachi

Publication date: 3 August 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2007.08811

zbMATH Keywords

fixed-parameter tractabilityparameterized complexitygraph burning

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (2)

Graph burning and non-uniform \(k\)-centers for small treewidth ⋮ Burn and win

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• The behavior of clique-width under graph operations and graph transformations
• Kernel bounds for disjoint cycles and disjoint paths
• Burning number of caterpillars
• Transmitting in the \(n\)-dimensional cube
• On transmitting delay in a distance-transitive strongly antipodal graph
• Bounds on the burning number
• Burning number of graph products
• Linear time solvable optimization problems on graphs of bounded clique-width
• An upper bound on the burning number of graphs
• Burning graphs: a probabilistic perspective
• Burning numbers of path forests and spiders
• Improved bounds for burning fence graphs
• On the burning number of \(p\)-caterpillars
• Burning the plane. Densities of the infinite Cartesian grid
• Burning number of theta graphs
• Parameterized algorithms for Graph Burning problem
• Approximation algorithms for graph burning
• Bounds on the burning numbers of spiders and path-forests
• Burning a graph is hard
• Burning spiders
• Graph burning: tight bounds on the burning numbers of path forests and spiders
• Parameterized Algorithms for Modular-Width
• Burning a Graph as a Model of Social Contagion
• Burning Two Worlds
• Spanning Trees with Many Leaves
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Routing and transmitting problems in de Bruijn networks
• Deciding First-Order Properties of Nowhere Dense Graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Kernelization Lower Bounds Through Colors and IDs
• Approximating rank-width and clique-width quickly
• A survey of graph burning
• The Burning Number of Directed Graphs: Bounds and Computational Complexity
• On the Relationship Between Clique-Width and Treewidth
• Parameterized Algorithms
• Graph-Theoretic Concepts in Computer Science
• How to Burn a Graph
• APX-hardness and approximation for the \(k\)-burning number problem

This page was built for publication: Parameterized complexity of graph burning