On the online track assignment problem

DOI10.1016/J.DAM.2012.01.002MaRDI QIDQ423916zbMATHOpenAlexFDO

Authors Marc Demange, Gabriele Di Stefano, Benjamin Leroy-Beaulieu

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

zbMATH Keywords

permutation graphsonline coloringcomparability graphsoverlap graphsonline bounded coloringtrack assignment

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Transportation, logistics and supply chain management (90B06) Discrete location and assignment (90B80)

Recommendations

• A Greedy On-Line Algorithm for thek-Track Assignment Problem
• The \(k\)-track assignment problem
• Trackless online algorithms for the server problem
• The \(k\)-Track assignment problem on partial orders
• The online stochastic generalized assignment problem
• Solvability of \(k\)-track assignment problem: a graph approach
• Randomized approximation and online algorithms for assignment problems
• On track procession assignment problem at the railway network sections
• scientific article; zbMATH DE number 1086921
• On-line \(k\)-truck problem and its competitive algorithms.

Cites work

• scientific article; zbMATH DE number 3606484 (Why is no real title available?)
• scientific article; zbMATH DE number 863477 (Why is no real title available?)
• A graph theoretical approach to the shunting problem
• A tutorial on the use of graph coloring for some problems in robotics
• Algorithmic graph theory and perfect graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• An on-line graph coloring algorithm with sublinear performance ratio
• Dispatching Buses in Parking Depots
• Fuzzy dispatching model and genetic algorithms for railyards operations
• On minimum \(k\)-modal partitions of permutations
• On the performance of the first-fit coloring algorithm on permutation graphs
• On-Line Coloring and Recursive Graph Theory
• On-line and first fit colorings of graphs
• On-line chain partitions of orders
• Parallel and On-Line Graph Coloring
• Parking buses in a depot using block patterns: a Benders decomposition approach for minimizing type mismatches
• Partitioning a weighted partial order
• Real-time dispatch of trams in storage yards
• Recoverable robustness for train shunting problems
• Routing Trains Through Railway Stations: Model Formulation and Algorithms
• Scheduling trams in the morning
• The train marshalling problem
• Track assignment
• Which claw-free graphs are perfectly orderable?

Cited in

(7)

• A graph theoretical approach to the shunting problem
• Generalised online colouring problems in overlap graphs
• A tree-based model for setting optimal train fare zones
• Track allocation in freight-train classification with mixed tracks
• Track assignment
• A survey on combinatorial optimization in dynamic environments
• An asymptotically optimal algorithm for online stacking

This page was built for publication: On the online track assignment problem

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