Disentangling the computational complexity of network untangling
From MaRDI portal
Publication:6151149
DOI10.1007/s00224-023-10150-yarXiv2204.02668OpenAlexW4388671702MaRDI QIDQ6151149
Pascal Kunz, Philipp Zschoche, Vincent Froese
Publication date: 9 February 2024
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2204.02668
Theory of computing (68Qxx) Graph theory (05Cxx) Discrete mathematics in relation to computer science (68Rxx)
Cites Work
- Unnamed Item
- Traveling salesman problems in temporal graphs
- Fundamentals of parameterized complexity
- Parameterized algorithm for eternal vertex cover
- Multistage graph problems on a global budget
- Almost 2-SAT is fixed-parameter tractable
- The node-deletion problem for hereditary properties is NP-complete
- Bin packing with fixed number of bins revisited
- Finding temporal paths under waiting time constraints
- The complexity of finding small separators in temporal graphs
- Temporal vertex cover with a sliding time window
- Sliding window temporal graph coloring
- Multistage vertex cover
- How fast can we reach a target vertex in stochastic temporal graphs?
- Parameterized complexity of Vertex Cover variants
- Parametrized complexity theory.
- The network-untangling problem: from interactions to activity timelines
- On temporal graph exploration
- Optimizing reachability sets in temporal graphs by delaying
- Integer Programming with a Fixed Number of Variables
- Tight Lower Bounds for the Complexity of Multicoloring
- Parameterized Algorithms
- Computing maximum matchings in temporal graphs.
- Edge exploration of temporal graphs
- On the complexity of \(k\)-SAT
- What Is Known About Vertex Cover Kernelization?
