Multistage Vertex Cover

DOI10.4230/LIPICS.IPEC.2019.14MaRDI QIDQ5875546zbMATH OpenOpenAlexFDO

Authors Till Fluschnik, Rolf Niedermeier, Valentin Rohm, Philipp Zschoche

Publication date 3 February 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/11475/pdf/LIPIcs-IPEC-2019-14.pdf/

zbMATH Keywords

dynamic graph problemsfixed-parameter tractabilitykernelizationNP-hardnesstemporal graphstime-evolving networksw[1-hardness]

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Recommendations

• Multistage vertex cover
• Temporal vertex cover with a sliding time window
• Temporal vertex cover with a sliding time window
• Multistage graph problems on a global budget
• Parameterized algorithmics for time-evolving structures: temporalizing and multistaging

Cited in

(14)

• A faster parameterized algorithm for temporal matching
• A simple rounding scheme for multistage optimization
• Target-based computer-assisted orchestration: complexity and approximation algorithms
• LP-based algorithms for multistage minimization problems
• Multistage knapsack
• Multistage vertex cover
• Feedback vertex set on Hamiltonian graphs
• A multistage view on 2-satisfiability
• Vertex cover meets scheduling
• Approximating multistage matching problems
• Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs
• Disentangling the computational complexity of network untangling
• Parameterized algorithmics for time-evolving structures: temporalizing and multistaging
• Multistage graph problems on a global budget

This page was built for publication: Multistage Vertex Cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875546)