Persistency in combinatorial optimization problems on matroids (Q5936456)
From MaRDI portal
scientific article; zbMATH DE number 1613395
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Persistency in combinatorial optimization problems on matroids |
scientific article; zbMATH DE number 1613395 |
Statements
Persistency in combinatorial optimization problems on matroids (English)
0 references
3 June 2002
0 references
Algorithms on matroids to find maximum weight bases or to solve the cardinality intersection problem of two matroids are analyzed to obtain a persistency partition of the elements into 1-persistent elements, which belong to all optimal solutions, 0-persistent ones which do not belong to any optimal solution, and non-persistent elements which belong to some, but not all optimal solutions. As an application, the persistency of edges of a bipartite graph with respect to maximum cardinality matching is characterized.
0 references
greedy algorithm
0 references
base
0 references
matroid intersection problem
0 references
persistency
0 references
