Name
Abstract | ||
|---|---|---|
The maximum matching and its related problems in convex bipartite graphs were studied by Clover (1967) and Lipski and Preparata (1981). This paper introduces circular convex bipartite graphs and considers the maximum matching and Hamiltonian circuit problems in these graphs. A bipartite 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 present linear time algorithms for finding a maximum matching and a Hamiltonian circuit in circular convex bipartite graphs. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0020-0190(95)00145-3 | Inf. Process. Lett. |
Keywords | Field | DocType |
hamiltonian circuit,maximum matching,circular convex bipartite graph,algorithms,bipartite graph | Complete bipartite graph,Discrete mathematics,Combinatorics,Indifference graph,Convex bipartite graph,Bipartite graph,Matching (graph theory),Hamiltonian path problem,3-dimensional matching,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
56 | 4 | 0020-0190 |
Citations | PageRank | References |
13 | 0.84 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Y. Daniel Liang | 1 | 153 | 14.93 |
| Norbert Blum | 2 | 13 | 0.84 |