Multistage vertex cover

DOI10.1007/S00224-022-10069-WMaRDI QIDQ2135630zbMATH OpenOpenAlexFDO

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

Publication date 9 May 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

data reductionNP-completenessparameterized algorithmicstemporal graphs

Mathematics Subject Classification ID

Graph theory (05Cxx) Theory of computing (68Qxx) 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
• Parameterized algorithmics for time-evolving structures: temporalizing and multistaging
• Multistage graph problems on a global budget

Cites work

• A multistage view on 2-satisfiability
• Approximating multistage matching problems
• Changing bases: multistage optimization for matroids and matchings
• Dynamic parameterized problems
• Dynamic parameterized problems and algorithms
• Facility location in evolving metrics
• Fast dynamic graph algorithms for parameterized problems
• scientific article; zbMATH DE number 7238962 (Why is no real title available?)
• Incremental list coloring of graphs, parameterized by conservation
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• LP-based algorithms for multistage minimization problems
• Maximum independent sets in 3- and 4-regular Hamiltonian graphs
• Multistage graph problems on a global budget
• Multistage knapsack
• Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs
• New limits to classical and quantum instance compression
• On problems without polynomial kernels
• On the complexity of reconfiguration problems
• On the parameterized complexity of dynamic problems
• Online multistage subset maximization problems
• Parameterized Algorithms for Diverse Multistage Problems
• Some consequences of non-uniform conditions on uniform classes
• Some simplified NP-complete graph problems
• Temporal vertex cover with a sliding time window
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Cited in

(10)

• Vertex cover meets scheduling
• As Time Goes By: Reflections on Treewidth for Temporal Graphs
• Multistage Vertex Cover
• Approximating multistage matching problems
• Multistage \(s-t\) path: confronting similarity with dissimilarity
• Disentangling the computational complexity of network untangling
• Parameterized algorithmics for time-evolving structures: temporalizing and multistaging
• Cluster editing for multi-layer and temporal graphs
• Temporal dominating set and temporal vertex cover under the lens of degree restrictions
• Timeline problems in temporal graphs: vertex cover vs. dominating set

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 Q2135630)