Minimum Cost Edge Subset Covering Exactly k Vertices of a Graph |
| |
Authors: | Jáan Plesník |
| |
Institution: | (1) Department of Numerical and Optimization Methods, Faculty of Mathematics, Physics and Informatics, Comenius University, Mlynska dolina, 84248 Bratislava, Slovakia |
| |
Abstract: | Given a graph G with nonnegative edge costs and an integer k, we consider the problem of finding an edge subset S of minimum total cost with respect to the constraint that S covers exactly k vertices of G. An O(n
3) algorithm is presented where n is the order of G. It is based on the author's previous paper dealing with a similar problem asking S to cover at least k vertices. |
| |
Keywords: | graph network edge cover polynomial algorithm |
本文献已被 SpringerLink 等数据库收录! |
|