Research map / Graph learning / Knowledge and temporal graphs
Sliding Window Temporal Graph Coloring
George B. Mertzios, Hendrik Molter, Viktor Zamaraev
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict exact temporal coloring to the vertex cover and give all other vertices a fresh color | Minimum SW-Temp. Coloring · Minimum SW-Temp. Coloring, parameterized by vertex cover number | additive approximation error: one | Improved |
| Generalize static coloring to require every active edge to be properly colored in every sliding Δ-window | Sliding Window Temporal Coloring · SW-Temp. Coloring | computational complexity | Hurt |
| Use the sliding-window requirement even when the underlying graph has a constant-size vertex cover | Sliding Window Temporal Coloring · 2-SW-Temp. k-Coloring, vertex cover number at most 2k+13 | computational complexity: 2k+13 | Hurt |
| Replace the full temporal instance with a maximum-matching-selected subset of time slots | Temporal Coloring · Temporal Coloring | kernel lifetime: T'≤m | Improved |
Closest papers by meaning
- Approximating Optimal Labelings for Temporal Connectivity (AAAI 2025 · similarity 0.86)
- How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs (AAAI 2025 · similarity 0.84)
- State Space Models on Temporal Graphs: A First-Principles Study (NeurIPS 2024 · similarity 0.84)
- A Deep Probabilistic Framework for Continuous Time Dynamic Graph Generation (AAAI 2025 · similarity 0.84)
- Temporal Triadic Closure: Finding Dense Substructures in Social Networks That Evolve over Time (AAAI 2025 · similarity 0.83)
- Expressive Power of Temporal Message Passing (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
