Routing and timetabling by topological search

MaRDI QIDQ1126868zbMATH OpenFDO

Authors Alexander Schrijver

Publication date 6 August 1998

Published in Documenta Mathematica (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/233084, http://www.emis.de/journals/DMJDMV/xvol-icm/17/Schrijver.MAN.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

closed curvescombinatorial optimizationcompact surfacedisjoint pathshomotopyhomotopy classesNP-completeperiodic timetableplanar graphsroutingsearch spacesurveytimetabling

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10) Deterministic scheduling theory in operations research (90B35)

Review text

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).

Recommendations

• scientific article; zbMATH DE number 4211829
• Periodic network optimization with different arc frequencies
• scientific article; zbMATH DE number 4083048
• Routing of railway carriages
• A Linear-Time Algorithm for the Homotopic Routing Problem in Grid Graphs

Cited in

(1)

• scientific article; zbMATH DE number 845618 (Why is no real title available?)

This page was built for publication: Routing and timetabling by topological search

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