On constrained minimum vertex covers of bipartite graphs: Improved algorithms Conference Paper

abstract

• Springer-Verlag Berlin Heidelberg 2001. The constrained minimum vertex cover problem on bipartite graphs arises from the extensively studied fault coverage problem for reconfigurable arrays. In this paper, we develop a new algorithm for the problem, in which classical results in matching theory and recently developed techniques in parameterized computation are nicely combined and extended. The algorithm is practically efficient with running time bounded by O(1.26k + kn), where k is the size of the constrained minimum vertex cover in the input graph. The algorithm is a significant improvement over the previous algorithms for the problem.

name of conference

• Graph-Theoretic Concepts in Computer Science, 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14-16, 2001, Proceedings

authors

• Chen, Jianer

published proceedings

• Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

• Chen, J., & Kanj, I. A.

complete list of authors

• Chen, J||Kanj, IA

publication date

• January 2001

published in

• Lecture Notes in Artificial Intelligence  Journal

International Standard Book Number (ISBN) 10

• 3540427074

International Standard Book Number (ISBN) 13

• 9783540427070

start page

• 55

end page

• 65

volume

• 2204