scientific article; zbMATH DE number 15374
Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)
[For the entire collection see Zbl 0698.00017.] For some practical applications (see [(*) \textit{G. Ehnert}, \textit{J. Harant} and \textit{H. Walther}, Teubner-Texte Math. 73, 31-35 (1985; Zbl 0599.90082)]) a problem is interesting which is illustrated in a not necessarily physically correct way as follows: Suppose an organization for time travels wants to carry out some trips into the past. The points of time visited are \(x_ 1,x_ 2,\dots,x_ f\), where \(x_ 1< x_ 2<\cdots <x_ f\). In order to execute these trips there are time travellers in \(r\) stations \(s_ 1,s_ 2,\dots,s_ r\) (their number is not limited in any station). But only the station can take a traveller into the past. A traveller at point \(x_ i\) can jump only in the forward direction, that means jumping to a point \(x_ j\) is possible only if \(x_ i< x_ j\) (which means \(i< j\)) or he can return to his station into the present time. Taking a traveller from station \(s_ k\) to point \(x_ i\) needs \(c^ k_{0i}\) energy units, jumping from \(x_ i\) to \(x_ j\) a traveller needs \(c_{ij}\) energy units and jumping from \(x_ i\) to \(s_ k\) he needs \(c^ k_{i0}\) units. We want to find a set of time travels such that every point \(x_ i\) is visited exactly once and such that the amount of energy is as small as possible. In (*) it was shown that this problem can be solved by a polynomial algorithm if \(r=1\). We show that it is NP-hard if \(r=2\).
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972019)
