Multistage graph problems on a global budget

DOI10.1016/J.TCS.2021.04.002zbMath1497.68380arXiv1912.04392OpenAlexW3153719637MaRDI 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

zbMATH Keywords

NP-hardnessparameterized complexityspace complexitytime-varying graphsmultivariate algorithmicstemporal graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (6)

Multistage vertex cover ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ Disentangling the computational complexity of network untangling ⋮ Approximating multistage matching problems ⋮ Approximating multistage matching problems ⋮ A faster parameterized algorithm for temporal matching

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

This page was built for publication: Multistage graph problems on a global budget