A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs (Q705040)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs |
scientific article; zbMATH DE number 2130927
| 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; zbMATH DE number 2130927 |
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
0.9092015
0 references
0.8998015
0 references
0.8987307
0 references
0.89514637
0 references
0.89480543
0 references
0.8934773
0 references
0.89331716
0 references
0.8902999
0 references
