Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 75 of 210
Back to Result List

The Cycle Embedding Problem

Please always quote using this URN: urn:nbn:de:0297-zib-52788
  • Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Ralf BorndörferORCiD, Marika Karbstein, Julika Mehrgardt, Markus Reuther, Thomas Schlechte
Document Type:ZIB-Report
Tag:cycle embedding problem; railway vehicle rotation scheduling; sequential coarse-first-fine-second planning approach
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Date of first Publication:2014/10/15
Series (Serial Number):ZIB-Report (14-37)
ISSN:1438-0064
Published in:Appeared in: Operations Research Proceedings 2014
DOI:https://doi.org/10.1007/978-3-319-28697-6_65
Licence (German):License LogoCreative Commons - Namensnennung-Nicht kommerziell
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.