The firebreak problem

DOI10.1002/net.21975zbMath1529.68191arXiv1901.07842MaRDI QIDQ6065343

David A. Pike, Jared Howell, Unnamed Author, Jessica Enright, Andrea C. Burgess, Unnamed Author

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 complexitytreewidthconnectivityseparationintersection graphskey players

Mathematics Subject Classification ID

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

Cites Work

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