The firebreak problem

DOI10.1002/NET.21975MaRDI QIDQ6065343zbMATH OpenFDO

Authors Andrea Burgess, Jessica Enright, Jared Howell, David A. Pike

Publication date 11 December 2023

Published in Networks (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityconnectivityintersection graphskey playersseparationtreewidth

Mathematics Subject Classification ID

Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Suppose we have a network that is represented by a graph $G$. Potentially a fire (or other type of contagion) might erupt at some vertex of $G$. We are able to respond to this outbreak by establishing a firebreak at $k$ other vertices of $G$, so that the fire cannot pass through these fortified vertices. The question that now arises is which $k$ vertices will result in the greatest number of vertices being saved from the fire, assuming that the fire will spread to every vertex that is not fully behind the $k$ vertices of the firebreak. This is the essence of the {sc Firebreak} decision problem, which is the focus of this paper. We establish that the problem is intractable on the class of split graphs as well as on the class of bipartite graphs, but can be solved in linear time when restricted to graphs having constant-bounded treewidth, or in polynomial time when restricted to intersection graphs. We also consider some closely related problems.

Recommendations

• scientific article; zbMATH DE number 2061798
• On a fire fighter's problem
• A fire fighter's problem
• The Firefighter Problem: A Structural Analysis
• The firefighter problem with more than one firefighter on trees
• The firefighter problem: further steps in understanding its complexity
• The Standard Response Fire Protection Siting Problem
• A graph theoretical approach to the firebreak locating problem
• The polygon burning problem

Cites work

• k-shredders ink-connected graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithmic Aspects of Graph Connectivity
• Algorithmic graph theory and perfect graphs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Complexity and approximability of the \(k\)-way vertex cut
• Easy problems for tree-decomposable graphs
• Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. XIII: The disjoint paths problem
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• Identifying sets of key players in a social network
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Minimal vertex separators of chordal graphs
• On Comparability and Permutation Graphs
• Parameterized graph separation problems
• Polynomial-Time Algorithm for the Leafage of Chordal Graphs
• Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The critical node detection problem in networks: a survey
• The Firefighter problem: a survey of results, directions and questions
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The Rectilinear Steiner Tree Problem is NP-Complete
• Treewidth and Pathwidth of Permutation Graphs
• Who's Who in Networks. Wanted: The Key Player

Cited in

(3)

• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• Distance-restricted firefighting on finite graphs
• Domination and cut problems on chordal graphs with bounded leafage

This page was built for publication: The firebreak problem

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