CIRCULAR CONVEX BIPARTITE GRAPHS - MAXIMUM MATCHING AND HAMILTONIAN CIRCUITS

Authors
LIANG YD BLUM N
Citation
Yd. Liang et N. Blum, CIRCULAR CONVEX BIPARTITE GRAPHS - MAXIMUM MATCHING AND HAMILTONIAN CIRCUITS, Information processing letters, 56(4), 1995, pp. 215-219
Citations number
13
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
56
Issue
4
Year of publication
1995
Pages
215 - 219
Database
ISI
SICI code
0020-0190(1995)56:4<215:CCBG-M>2.0.ZU;2-Z
Abstract
The maximum matching and its related problems in convex bipartite grap hs were studied by Clover (1967) and Lipski and Preparata (1981). This paper introduces circular convex bipartite graphs and considers the m aximum matching and Hamiltonian circuit problems in these graphs. A bi partite graph G = (A, B, E) is circular convex on the vertex set A if A can be ordered on a circle so that for each element b in the vertex set B the elements of A connected to b form a circular are of A. We pr esent linear time algorithms for finding a maximum matching and a Hami ltonian circuit in circular convex bipartite graphs.