Routing and timetabling by topological search (Q1126868)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Routing and timetabling by topological search |
scientific article; zbMATH DE number 1184405
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Routing and timetabling by topological search |
scientific article; zbMATH DE number 1184405 |
Statements
Routing and timetabling by topological search (English)
0 references
6 August 1998
0 references
This is a survey paper. The author shows how decomposing the search space into homotopy classes can help in finding solutions to combinatorial optimization problems. The method is illustrated on two specific classes of NP-complete problems: the \(k\) disjoint paths problem for directed planar graphs when \(k\) is fixed, and the problem of finding a periodic timetable (applied to the Dutch railway timetable).
0 references
homotopy
0 references
disjoint paths
0 references
routing
0 references
timetabling
0 references
closed curves
0 references
compact surface
0 references
survey
0 references
search space
0 references
homotopy classes
0 references
combinatorial optimization
0 references
NP-complete
0 references
planar graphs
0 references
periodic timetable
0 references
0.7378208637237549
0 references
0.7375614047050476
0 references
0.706062376499176
0 references
