The Complexity of Transitively Orienting Temporal Graphs

DOI10.4230/lipics.mfcs.2021.75arXiv2102.06783OpenAlexW3187055303MaRDI QIDQ6168495

Paul G. Spirakis, George B. Mertzios, Malte Renken, Philipp Zschoche, Hendrik Molter

Publication date: 8 August 2023

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

zbMATH Keywords

polynomial-time algorithmtransitive closuresatisfiabilityNP-hardnesstransitive orientationtemporal graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks

This page was built for publication: The Complexity of Transitively Orienting Temporal Graphs