Multistage vertex cover

DOI10.1007/s00224-022-10069-wOpenAlexW2947863886MaRDI QIDQ2135630

Till Fluschnik, Philipp Zschoche, Valentin Rohm, Rolf Niedermeier

Publication date: 9 May 2022

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1906.00659

zbMATH Keywords

data reductionNP-completenessparameterized algorithmicstemporal graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Graph theory (05Cxx)

Related Items (4)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ Disentangling the computational complexity of network untangling ⋮ Approximating multistage matching problems

Cites Work

• Unnamed Item
• Incremental list coloring of graphs, parameterized by conservation
• On the parameterized complexity of reconfiguration problems
• On the complexity of reconfiguration problems
• Maximum independent sets in 3- and 4-regular Hamiltonian graphs
• Dynamic parameterized problems
• Some consequences of non-uniform conditions on uniform classes
• Multistage graph problems on a global budget
• On the parameterized complexity of dynamic problems
• On problems without polynomial kernels
• Some simplified NP-complete graph problems
• Temporal vertex cover with a sliding time window
• Online multistage subset maximization problems
• LP-based algorithms for multistage minimization problems
• Multistage knapsack
• A multistage view on 2-satisfiability
• Fast Dynamic Graph Algorithms for Parameterized Problems
• New Limits to Classical and Quantum Instance Compression
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Dynamic Parameterized Problems and Algorithms
• Changing Bases: Multistage Optimization for Matroids and Matchings
• Facility Location in Evolving Metrics
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Temporal graph classes: a view through temporal separators
• Approximating multistage matching problems
• Parameterized Algorithms for Diverse Multistage Problems
• Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs

This page was built for publication: Multistage vertex cover