Open Research Index

The directed temporal exploration problem

Marcelo Garlet Milani, Lucas Picasarri-Arrieta, Chaoliang Tang, Hehui Wu

arXivarxiv/2609.34339Sep 28, 2026cs.DSscore 0

We study the temporal exploration problem on temporal digraphs. We prove that a lifetime of $O(n^2)$ suffices to guarantee the existence of a temporal exploration on always-unilateral temporal digraphs. We complement this with a $Ω(n^2)$ lower bound, even in the case where each snapshot has maximum undirected degree 2; for always-strong temporal digraphs, the lower bound still holds even if the maximum undirected degree is 3. This stands in stark contrast with the undirected setting. For the large minimum degree setting, we show that a lifetime of $4n/3 - 1$ is sufficient and necessary for…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2609.34339
curl -X POST /api/v1/records/arxiv/2609.34339/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.34339/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'