Multistage graph problems on a global budget
From MaRDI portal
Publication:831134
DOI10.1016/j.tcs.2021.04.002zbMath1497.68380arXiv1912.04392MaRDI QIDQ831134
Andrej Sajenko, Malte Renken, Klaus Heeger, Rolf Niedermeier, Frank Kammer, Anne-Sophie Himmel
Publication date: 10 May 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1912.04392
NP-hardness; parameterized complexity; space complexity; time-varying graphs; multivariate algorithmics; temporal graphs
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q27: Parameterized complexity, tractability and kernelization
Related Items
Approximating multistage matching problems, Approximating multistage matching problems, Multistage \(s-t\) path: confronting similarity with dissimilarity, Disentangling the computational complexity of network untangling, A faster parameterized algorithm for temporal matching, Multistage vertex cover
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Incremental list coloring of graphs, parameterized by conservation
- Dynamic parameterized problems
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- On the parameterized complexity of dynamic problems
- Going weighted: parameterized algorithms for cluster editing
- Parameterized dynamic cluster editing
- Temporal matching
- On the space and circuit complexity of parameterized problems: classes and completeness
- Contracting graphs to paths and trees
- A refined search tree technique for dominating set on planar graphs
- Streaming Kernelization
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
- Nondeterminism within $P^ * $
- Cluster Editing in Multi-Layer and Temporal Graphs.
- Changing Bases: Multistage Optimization for Matroids and Matchings
- Facility Location in Evolving Metrics
- Temporal Network Theory
- Computing maximum matchings in temporal graphs.
- Space-efficient, fast and exact routing in time-dependent road networks
- Multistage Vertex Cover
- Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs
