Cover Image

Recognizing and Realizing Temporal Reachability Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Erlebach, Thomas, Michail, Othon, Morawietz, Nils
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs
by: Casteigts, Arnaud, et al.
Published: (2024)

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
by: Casteigts, Arnaud, et al.
Published: (2026)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
Published: (2025)

Parameterized Local Search for Max $c$-Cut
by: Garvardt, Jaroslav, et al.
Published: (2024)

The Parameter Report: An Orientation Guide for Data-Driven Parameterization
by: Komusiewicz, Christian, et al.
Published: (2025)

A Parameterized-Complexity Framework for Finding Local Optima
by: Ganian, Robert, et al.
Published: (2026)

Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
by: Grüttemeier, Niels, et al.
Published: (2025)

The Descriptive Complexity of Relation Modification Problems
by: Chudigiewitsch, Florian, et al.
Published: (2026)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

Realizing Graphs with Cut Constraints
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

Maximum Reachability Orientation of Mixed Graphs
by: Hörsch, Florian
Published: (2025)

Recognizing Visibility Graphs of Polygons with Holes and Internal-External Visibility Graphs of Polygons
by: Boomari, Hossein, et al.
Published: (2018)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
by: Balzereit, Kaja, et al.
Published: (2024)

Temporal Reachability Dominating Sets: contagion in temporal graphs
by: Kutner, David C., et al.
Published: (2023)

Recognizing 2-Layer and Outer $k$-Planar Graphs
by: Kobayashi, Yasuaki, et al.
Published: (2024)

Reachability In Simple Neural Networks
by: Sälzer, Marco, et al.
Published: (2022)

Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules
by: Hirahara, Shuichi, et al.
Published: (2025)

The Complexity of Recognizing Facets for the Knapsack Polytope
by: Chen, Rui, et al.
Published: (2022)

Dynamic Planar Graph Isomorphism is in DynFO
by: Datta, Samir, et al.
Published: (2026)

Realizing Metric Spaces with Convex Obstacles
by: Kisfaludi-Bak, Sándor, et al.
Published: (2025)

Reachability of Fair Allocations via Sequential Exchanges
by: Igarashi, Ayumi, et al.
Published: (2023)

Inner-approximate Reachability Computation via Zonotopic Boundary Analysis
by: Ren, Dejin, et al.
Published: (2024)

Galois Energy Games: To Solve All Kinds of Quantitative Reachability Problems
by: Lemke, Caroline, et al.
Published: (2025)

Realization of Temporally Connected Graphs Based on Degree Sequences
by: Casteigts, Arnaud, et al.
Published: (2025)

Temporal Cycle Detection and Acyclic Temporization
by: de Andrade, Davi, et al.
Published: (2025)

Recognizing Sumsets is NP-Complete
by: Abboud, Amir, et al.
Published: (2024)

Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity
by: Oettershagen, Lutz, et al.
Published: (2025)

Matching and Edge Cover in Temporal Graphs
by: Cioni, Lapo, et al.
Published: (2025)

Reachability in Geometrically $d$-Dimensional VASS
by: Fu, Yuxi, et al.
Published: (2025)

The Reachability Problem for Neural-Network Control Systems
by: Schilling, Christian, et al.
Published: (2024)

Specification and Automatic Verification of Computational Reductions
by: Grange, Julien, et al.
Published: (2024)

Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics
by: Cauvi, Justine, et al.
Published: (2025)

The Complexity of Transitively Orienting Temporal Graphs
by: Mertzios, George B., et al.
Published: (2021)

Breaking the Temporal Complexity Barrier: Bucket Calculus for Parallel Machine Scheduling
by: Mohammad, Noor Islam S.
Published: (2026)

Temporal Graph Realization With Bounded Stretch
by: Mertzios, George B., et al.
Published: (2025)

The Computational Complexity of Factored Graphs
by: Gupta, Shreya, et al.
Published: (2024)

Outer-(ap)RAC Graphs
by: Förster, et al.
Published: (2024)

Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
by: Xu, Jeff
Published: (2024)

The Parameterized Complexity of Coloring Mixed Graphs
by: Lauerbach, Antonio, et al.
Published: (2026)

On the Complexity of Problems on Tree-structured Graphs
by: Bodlaender, Hans L., et al.
Published: (2022)