AI Paper Atlas

Research map / Graph learning / Knowledge and temporal graphs

Sliding Window Temporal Graph Coloring

George B. Mertzios, Hendrik Molter, Viktor Zamaraev

AAAI 2019 · Graph learning › Knowledge and temporal graphs · approach: Temporal graph neural architectures · 19 citations (OpenAlex)

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 changedWhereMeasuredEffect
Restrict exact temporal coloring to the vertex cover and give all other vertices a fresh colorMinimum SW-Temp. Coloring · Minimum SW-Temp. Coloring, parameterized by vertex cover numberadditive approximation error: oneImproved
Generalize static coloring to require every active edge to be properly colored in every sliding Δ-windowSliding Window Temporal Coloring · SW-Temp. Coloringcomputational complexityHurt
Use the sliding-window requirement even when the underlying graph has a constant-size vertex coverSliding Window Temporal Coloring · 2-SW-Temp. k-Coloring, vertex cover number at most 2k+13computational complexity: 2k+13Hurt
Replace the full temporal instance with a maximum-matching-selected subset of time slotsTemporal Coloring · Temporal Coloringkernel lifetime: T'≤mImproved

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy