Routing and timetabling by topological search (Q1126868)
From MaRDI portal
!
WARNING
This is the item page for this Wikibase entity, intended for internal use and editing purposes.
Please use the normal view instead:
scientific article; zbMATH DE number 1184405
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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.7375614047050476
0 references
0.706062376499176
0 references
0.7054179906845093
0 references
