No label defined (Q4945799)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1424550
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1424550 |
Statements
23 March 2000
0 references
Steiner trees
0 references
combinatorial optimization
0 references
0.8551364541053772
0 references
0.8345155715942383
0 references
0.7969943881034851
0 references
0.795512318611145
0 references
In the well-known Steiner problem in graphs specific nodes have to be connected by a least cost network which may contain additional nodes. Hence nodes have 2 levels of service: full service and (possibly) no service. The authors generalize this problem to one, where each of the nodes may have one of \(r\) possible service levels. While this problem is obviously NP hard in general, the authors show that the problem can be solved in polynomial time for series-parallel graphs which are subgraphs of so-called 2-trees. For the entire collection see [Zbl 0932.00010].
0 references
