Deleting edges to restrict the size of an epidemic: a new application for treewidth
From MaRDI portal
Publication:1635713
DOI10.1007/s00453-017-0311-7zbMath1388.05174arXiv1504.05773OpenAlexW2607316446MaRDI QIDQ1635713
Publication date: 1 June 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.05773
Epidemiology (92D30) Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth ⋮ On critical node problems with vulnerable vertices ⋮ Deleting edges to restrict the size of an epidemic in temporal networks ⋮ Optimizing reachability sets in temporal graphs by delaying ⋮ Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ Assigning times to minimise reachability in temporal graphs ⋮ Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs ⋮ Unnamed Item ⋮ Reducing reachability in temporal graphs: towards a more realistic model of real-world spreading processes
Uses Software
Cites Work
- Unnamed Item
- Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
- Monadic second-order evaluations on tree-decomposable graphs
- On the computational complexity of vertex integrity and component order connectivity
- Graph minors. III. Planar tree-width
- The node-deletion problem for hereditary properties is NP-complete
- Some complexity results about threshold graphs
- Treewidth. Computations and approximations
- Fixed-parameter tractability of graph modification problems for hereditary properties
- On the NP-hardness of edge-deletion and -contraction problems
- Algorithmic graph theory and perfect graphs
- Faster Parameterized Algorithms for Deletion to Split Graphs
- The Complexity and Approximability of Minimum Contamination Problems
- Easy problems for tree-decomposable graphs
- Complexity of Finding Embeddings in a k-Tree
- The complexity of some edge deletion problems
- A linear time algorithm for finding tree-decompositions of small treewidth
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Node-and edge-deletion NP-complete problems
- Complexity classification of some edge modification problems
