An analysis of the parameterized complexity of periodic timetabling

DOI10.1007/s10951-021-00719-1OpenAlexW4213108070MaRDI QIDQ2142676

Julian Reisch, Niels Lindner

Publication date: 27 May 2022

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-021-00719-1

zbMATH Keywords

treewidthbranchwidthperiodic timetablingperiodic event scheduling problemcarvingwidth

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Transportation, logistics and supply chain management (90B06) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Traffic problems in operations research (90B20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Introducing TimPassLib -- a library for integrated periodic timetabling and passenger routing ⋮ Forward and line-based cycle bases for periodic timetabling

Uses Software

• NetworkX
• PESPLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• On the complexity of some colorful problems parameterized by treewidth
• Graph minors. III. Planar tree-width
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Graph minors. X: Obstructions to tree-decomposition
• Call routing and the ratcatcher
• Treewidth. Computations and approximations
• A strongly polynomial algorithm for the minimum cost tension problem
• Parameterized complexity of machine scheduling: 15 open problems
• Graph minors. XIII: The disjoint paths problem
• Positive-instance driven dynamic programming for treewidth
• Square roots of minor closed graph classes
• Characterizing graphs of small carving-width
• Solving Periodic Timetable Optimisation Problems by Modulo Simplex Calculations
• A Mathematical Model for Periodic Scheduling Problems
• Constructive linear time algorithms for branchwidth
• Graph Bisection with Pareto Optimization
• The Effect of Planarization on Width
• Reducibility among Combinatorial Problems
• A Matching Approach for Periodic Timetabling
• Periodic Timetable Optimization in Public Transport
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Parallel algorithms for series parallel graphs and graphs with treewidth two

This page was built for publication: An analysis of the parameterized complexity of periodic timetabling