Loading...
Please wait, while we are loading the content...
Similar Documents
Angewandte Mathematik Und Informatik Universit at Zu K Oln Steiner-diagrams and K-star-hubs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Oertel, Peter |
| Copyright Year | 2000 |
| Abstract | In this report, we introduce and study two problems derived from reload problems in transport logistics. Given a transitive digraph G = (V; A; w) with nonnegative arc weights and a set of demand arcs B, the objective of the Steiner Diagram Problem is to nd an acyclic set of arcs S of minimal cost, whose transitive closure contains B. This problem is N P-complete in the general case and has some interesting structural properties that make it polynomially solvable if the size of B is bounded by a constant, the triangle inequality holds in A and A is transitively closed. Secondly, we discuss a weighted edge cover problem with k cost functions on the vertices and give an eecient algorithm for the case k = 2. |
| File Format | PDF HTM / HTML |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |