Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102500
Title: Ordering metro lines by block crossings
Authors: Fink, M.
Pupyrev, S.
Issue Date: 2013
Citation: Fink M. Ordering metro lines by block crossings / M. Fink, S. Pupyrev. — DOI 10.1007/978-3-642-40313-2_36 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2013. — Vol. 8087 LNCS. — P. 397-408.
Abstract: A problem that arises in drawings of transportation networks is to minimize the number of crossings between different transportation lines. While this can be done efficiently under specific constraints, not all solutions are visually equivalent. We suggest merging crossings into block crossings, that is, crossings of two neighboring groups of consecutive lines. Unfortunately, minimizing the total number of block crossings is NP-hard even for very simple graphs. We give approximation algorithms for special classes of graphs and an asymptotically worst-case optimal algorithm for block crossings on general graphs. © 2013 Springer-Verlag.
Keywords: ALL SOLUTIONS
GENERAL GRAPH
METRO LINES
NUMBER OF BLOCKS
OPTIMAL ALGORITHM
SPECIAL CLASS
TRANSPORTATION LINE
TRANSPORTATION NETWORK
COMPUTER SCIENCE
APPROXIMATION ALGORITHMS
URI: http://hdl.handle.net/10995/102500
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84885209692
PURE ID: 858419
3df2c5aa-e828-48db-adf4-54b67b7172bd
ISSN: 3029743
ISBN: 9783642403125
DOI: 10.1007/978-3-642-40313-2_36
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84885209692.pdf800,66 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.