1,721,140 research outputs found
Track assignment
No full textWe consider a station in which several trains might stop at the same track at the same time. The trains might enter and leave the
station from both sides, but the arrival and departure times and directions are fixed according to a given time table. The problem
is to assign tracks to the trains such that they can enter and leave the station on time without being blocked by any other train. We
consider some variation of the problem on linear time tables as well as on cyclic time tables and show how to solve them as a graph
coloring problem on special graph classes. One of these classes are the so called circular arc containment graphs for which we give
an optimal O(n log n) coloring algorithm
Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings
No full textThe paper presents general results about the gathering problem on graphs. A team of robots placed at the vertices of a graph, have to meet at some vertex and remain there. Robots operate in LookâComputeâMove cycles; in one cycle, a robot perceives the current configuration in terms of robots disposal (Look), decides whether to move towards one of its neighbors (Compute), and in the positive case makes the computed move (Move). Cycles are performed asynchronously for each robot. So far, the goal has been to provide feasible resolution algorithms with respect to different assumptions about the capabilities of the robots as well as the topology of the underlying graph. In this paper, we are interested in studying the quality of the resolution algorithms in terms of the minimum number of asynchronous moves performed by the robots to accomplish the gathering task. We provide results for general graphs that suggest resolution techniques and provide feasibility properties. Then, we apply the obtained theory on specific topologies like trees and rings. The resulting algorithms for trees and rings are then compared with the existing ones, hence showing how the old solutions can be far apart from the optimum
- …
