A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs (Q705040): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Easy problems for tree-decomposable graphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3097395 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Steiner \(k\)-edge connected subgraph polyhedra / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3684121 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4252334 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4952178 / rank | |||
Normal rank | |||
Revision as of 16:44, 7 June 2024
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
