On the online track assignment problem
From MaRDI portal
Publication:423916
DOI10.1016/j.dam.2012.01.002zbMath1238.90088OpenAlexW2001487170MaRDI QIDQ423916
Marc Demange, Benjamin Leroy-Beaulieu, Gabriele Di Stefano
Publication date: 30 May 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2012.01.002
comparability graphspermutation graphsonline coloringoverlap graphsonline bounded coloringtrack assignment
Applications of graph theory (05C90) Transportation, logistics and supply chain management (90B06) Discrete location and assignment (90B80) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
A survey on combinatorial optimization in dynamic environments ⋮ An asymptotically optimal algorithm for online stacking ⋮ A tree-based model for setting optimal train fare zones ⋮ Generalised online colouring problems in overlap graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the performance of the first-fit coloring algorithm on permutation graphs
- Which claw-free graphs are perfectly orderable?
- Parking buses in a depot using block patterns: a Benders decomposition approach for minimizing type mismatches
- Partitioning a weighted partial order
- A tutorial on the use of graph coloring for some problems in robotics
- On minimum \(k\)-modal partitions of permutations
- An on-line graph coloring algorithm with sublinear performance ratio
- Scheduling trams in the morning
- On-line chain partitions of orders
- The train marshalling problem
- Fuzzy dispatching model and genetic algorithms for railyards operations
- Real-time dispatch of trams in storage yards
- Algorithmic graph theory and perfect graphs
- Track assignment
- On-line and first fit colorings of graphs
- On-Line Coloring and Recursive Graph Theory
- Parallel and On-Line Graph Coloring
- Routing Trains Through Railway Stations: Model Formulation and Algorithms
- Dispatching Buses in Parking Depots
- Algorithms for a maximum clique and a maximum independent set of a circle graph