Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth
From MaRDI portal
Publication:3467872
DOI10.1007/978-3-319-26626-8_42zbMath1475.92159OpenAlexW3101615909MaRDI QIDQ3467872
Publication date: 5 February 2016
Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)
Full work available at URL: http://dspace.stir.ac.uk/bitstream/1893/25354/1/Algorithmica_Springer.pdf
Related Items
Linear kernels for separating a graph into components of bounded size ⋮ Parameterized complexity of critical node cuts ⋮ Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms ⋮ Unnamed Item ⋮ Unnamed Item
Cites Work
- 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
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- 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
