A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs (Q705040)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs |
scientific article |
Statements
A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs (English)
0 references
25 January 2005
0 references
The result is mentioned in the title and comes neither new [\textit{K. Takamizawa, T. Nishizeki} and \textit{N. Saito}, J. Assoc. Comput. Mach. 29, 623--641 (1982; Zbl 0485.68055)] nor surprising, since series-parallel graphs have treewidth at most two.
0 references
series-parallel graph
0 references
feedback vertex set
0 references
linear algorithm
0 references
