| Autor: |
Hackfeld, Jan, Koster, Arie M. C. A. |
| Zdroj: |
Journal of Combinatorial Optimization; Apr2018, Vol. 35 Issue 3, p853-859, 7p |
| Abstrakt: |
A simple connected graph G with 2n vertices is said to be k-extendable for an integer k with 0 if G contains a perfect matching and every matching of cardinality k in G is a subset of some perfect matching. Lakhal and Litzler (Inf Process Lett 65(1):11-16, 1998) discovered a polynomial algorithm that decides whether a bipartite graph is k-extendable. For general graphs, however, it has been an open problem whether there exists a polynomial algorithm. The new result presented in this paper is that the extendability problem is co-NP-complete. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
Full text from SpringerLink