The complexity of transitively orienting temporal graphs

DOI10.1016/J.JCSS.2025.103630MaRDI QIDQ7007130zbMATH OpenFDO

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

Publication date 26 March 2025

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

Full work available at URL https://doi.org/10.1016/J.JCSS.2025.103630

zbMATH Keywords

NP-hardnesspolynomial-time algorithmsatisfiabilitytemporal graphtransitive closuretransitive orientation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A simplified NP-complete satisfiability problem
• Algorithmic graph theory and perfect graphs
• Assigning times to minimise reachability in temporal graphs
• Cluster Editing in Multi-Layer and Temporal Graphs.
• Computing maximal cliques in link streams
• Computing maximum matchings in temporal graphs
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Connectivity and inference problems for temporal networks
• Deleting edges to restrict the size of an epidemic in temporal networks
• Efficient graph representations
• Evaluating temporal graphs built from texts via transitive reduction
• Finding temporal paths under waiting time constraints
• How fast can we reach a target vertex in stochastic temporal graphs?
• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 6472574 (Why is no real title available?)
• scientific article; zbMATH DE number 7788370 (Why is no real title available?)
• Maintaining knowledge about temporal intervals
• Modular decomposition and transitive orientation
• On Comparability and Permutation Graphs
• On temporal graph exploration
• On the size and the approximability of minimum temporally connected subgraphs
• Orienting graphs to optimize reachability
• Sliding window temporal graph coloring
• Some simplified NP-complete graph problems
• Temporal cliques admit sparse spanners
• Temporal graph classes: a view through temporal separators
• Temporal network optimization subject to connectivity constraints
• Temporal network theory
• Temporal vertex cover with a sliding time window
• The complexity of finding small separators in temporal graphs
• The complexity of optimal design of temporally connected graphs
• The complexity of satisfiability problems
• The Complexity of Transitively Orienting Temporal Graphs
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial

This page was built for publication: The complexity of transitively orienting temporal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7007130)