Clearing directed subgraphs by mobile agents. Variations on covering with paths
DOI10.1016/j.jcss.2018.11.002zbMath1421.68116OpenAlexW2748092602WikidataQ128882891 ScholiaQ128882891MaRDI QIDQ1741492
Paweł Żyliński, Mia Persson, Andrzej Lingas, Dariusz Dereniowski, Dorota Osula
Publication date: 3 May 2019
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2018.11.002
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Constrained multilinear detection and generalized graph motifs
- Brushing with additional cleaning restrictions
- Directed Steiner trees with diffusion costs
- Faster algorithms for finding and counting subgraphs
- Cleaning with brooms
- On the computational complexity of path cover problems
- Cleaning a network with brushes
- On the complexity of paths avoiding forbidden pairs
- Parallel cleaning of a network with brushes
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Narrow sieves for parameterized paths and packings
- Complexity of the path avoiding forbidden pairs problem revisited
- Brushing without capacity restrictions
- The number of trees
- Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
- Directed Steiner Tree with Branching Constraint
- A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
- On Directed Steiner Trees with Multiple Roots
- Lehman's Theorem and the Directed Steiner Tree Problem
- Faster Algebraic Algorithms for Path and Packing Problems
- On structured digraphs and program testing
- On Path Cover Problems in Digraphs and Applications to Program Testing
- Approximating Directed Steiner Problems via Tree Embedding
- Approximation Algorithms for Directed Steiner Problems
- LIMITS and Applications of Group Algebras for Parameterized Problems
- Linear Programming Hierarchies Suffice for Directed Steiner Tree
This page was built for publication: Clearing directed subgraphs by mobile agents. Variations on covering with paths
