Sliding window temporal graph coloring

DOI10.1016/j.jcss.2021.03.005zbMath1473.68123arXiv1811.04753OpenAlexW3140257771MaRDI QIDQ2037193

Hendrik Molter, George B. Mertzios, Victor Zamaraev

Publication date: 30 June 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

channel assignmentNP-hardnessfixed-parameter tractabilityparameterized complexitytime-varying graphlink stream

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (10)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Temporal interval cliques and independent sets ⋮ Sharp Thresholds in Random Simple Temporal Graphs ⋮ Disentangling the computational complexity of network untangling ⋮ Untangling temporal graphs of bounded degree ⋮ Computing maximum matchings in temporal graphs ⋮ Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs ⋮ Coloring temporal graphs ⋮ Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem ⋮ Temporal vertex cover with a sliding time window

Uses Software

• cliques

Cites Work

• Unnamed Item
• Unnamed Item
• Traveling salesman problems in temporal graphs
• A simplified NP-complete satisfiability problem
• Computing maximal cliques in link streams
• Some simplified NP-complete graph problems
• Which problems have strongly exponential complexity?
• Temporal network optimization subject to connectivity constraints
• The complexity of finding small separators in temporal graphs
• Temporal vertex cover with a sliding time window
• The complexity of optimal design of temporally connected graphs
• On temporal graph exploration
• DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
• Flooding Time of Edge-Markovian Evolving Graphs
• On coloring problems for two-season multigraphs
• Exploration of Periodically Varying Graphs
• Nondeterminism within $P^ * $
• Kernelization Lower Bounds by Cross-Composition
• Reducibility among Combinatorial Problems
• Changing Bases: Multistage Optimization for Matroids and Matchings
• Randomized Rumor Spreading in Dynamic Graphs
• The complexity of satisfiability problems
• Parameterized Algorithms
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• Connectivity and inference problems for temporal networks
• Temporal graph classes: a view through temporal separators
• On the complexity of \(k\)-SAT

This page was built for publication: Sliding window temporal graph coloring