Solving NP-hard problems in 'almost trees': vertex cover (Q1062757): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q56505202, #quickstatements; #temporary_batch_1704605156744 |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 00:29, 31 January 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Solving NP-hard problems in 'almost trees': vertex cover |
scientific article |
Statements
Solving NP-hard problems in 'almost trees': vertex cover (English)
0 references
1985
0 references
In the paper a new algorithm which finds a minimum vertex cover in a graph G, is proposed. Its complexity depends linearly on the number of vertices of G and exponentially on the maximum a over all biconnected components of the graph, where a is defined as the minimum number of edges that must be added to a tree to produce G. A parallel implementation of the algorithm is also given.
0 references
algorithm
0 references
minimum vertex cover
0 references
parallel implementation
0 references
