Cover Image

Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Meusel, Julia, Müller-Hannemann, Matthias, Reinhardt, Klaus
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity Discrete Mathematics 68R10 (Primary), 68Q25 (Secondary)
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Optimal Hardness of Online Algorithms for Large Independent Sets
by: Gamarnik, David, et al.
Published: (2025)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Coloring Hardness on Low Twin-Width Graphs
by: Bonnet, Édouard
Published: (2025)

A scalable clustering algorithm to approximate graph cuts
by: Suchan, Leo, et al.
Published: (2023)

Optimal Discretization is Fixed-parameter Tractable
by: Kratsch, Stefan, et al.
Published: (2020)

Answering Related Questions
by: Bonnet, Édouard
Published: (2025)

Balanced connected partitions of edge-weighted graphs: Hardness and solving methods
by: Davari, Morteza, et al.
Published: (2025)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

An Explicit and Efficient $O(n^2)$-Time Algorithm for Sorting Sumsets
by: Mundhra, S.
Published: (2025)

Fundamentals of Partial Rejection Sampling
by: Jerrum, Mark
Published: (2021)

Sublinear-Time Computation in the Presence of Online Erasures
by: Kalemaj, Iden, et al.
Published: (2021)

The Upper Clique Transversal Problem
by: Milanič, Martin, et al.
Published: (2023)

Interval Graphs are Reconstructible
by: Heinrich, Irene, et al.
Published: (2025)

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
by: Laekhanukit, Bundit
Published: (2024)

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
by: Alpay, Faruk, et al.
Published: (2026)

A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
by: Hougardy, Stefan, et al.
Published: (2025)

An Algorithm to Recover Shredded Random Matrices
by: Atamanchuk, Caelan, et al.
Published: (2023)

Regenerative Ulam-von Neumann Algorithm: An Innovative Markov chain Monte Carlo Method for Matrix Inversion
by: Ghosh, Soumyadip, et al.
Published: (2024)

Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
by: Buchbinder, Niv, et al.
Published: (2024)

Concurrency Constrained Scheduling with Tree-Like Constraints
by: Bodlaender, Hans L., et al.
Published: (2025)

Shortest Paths in a Weighted Simplicial Complex
by: Chakraborty, Sukrit, et al.
Published: (2025)

Reconfiguring homomorphisms to reflexive graphs via a simple reduction
by: Mühlenthaler, Moritz, et al.
Published: (2024)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
by: Bonnet, Édouard, et al.
Published: (2026)

Cluster Vertex Deletion Problems on Cubic Graphs
by: Rusu, Irena
Published: (2025)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
by: Avila, Tatiana Rocha, et al.
Published: (2026)

Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
by: Feldman, Moran, et al.
Published: (2026)

On Solving Reachability in Grid Digraphs using a Psuedoseparator
by: Jain, Rahul, et al.
Published: (2019)

Exact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile
by: Gu, Qian-Ping, et al.
Published: (2025)

Mim-Width is paraNP-complete
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
by: Morse, Gregory, et al.
Published: (2026)

Pliability and Approximating Max-CSPs
by: Romero, Miguel, et al.
Published: (2019)

On the Complexity of Distance-$d$ Independent Set Reconfiguration
by: Hoang, Duc A.
Published: (2022)

Degree Realization by Bipartite Cactus Graphs
by: Bar-Noy, Amotz, et al.
Published: (2025)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
by: Demaine, Erik D., et al.
Published: (2024)

Parallel Algorithms for Group Isomorphism via Code Equivalence
by: Levet, Michael
Published: (2026)

Dynamic Traffic Assignment for Public Transport with Vehicle Capacities
by: Patzner, Julian, et al.
Published: (2024)

Probabilistic Analysis of Edge Elimination for Euclidean TSP
by: Zhong, Xianghui
Published: (2018)