Circular Convex Bipartite Graphs: Maximum Matching and Hamiltonian Circuits

Y. Daniel Liang; Norbert Blum

doi:10.1016/0020-0190(95)00145-3

Circular Convex Bipartite Graphs: Maximum Matching and Hamiltonian Circuits

Y. Daniel Liang, Norbert Blum

Computer Science

Research output: Contribution to journal › Article › peer-review

29 Scopus citations

Abstract

The maximum matching and its related problems in convex bipartite graphs were studied by Glover (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 arc of A . We present linear time algorithms for finding a maximum matching and a Hamiltonian circuit in circular convex bipartite graphs.

Original language	American English
Journal	Information Processing Letters
Volume	56
DOIs	https://doi.org/10.1016/0020-0190(95)00145-3
State	Published - Nov 24 1995

Disciplines

Computer Sciences

Keywords

Algorithms
Circular convex bipartite graph
Convex bipartite graph
Hamiltonian circuit
Maximum matching

Access to Document

10.1016/0020-0190(95)00145-3License: Unspecified

Cite this

@article{72fb6dd756b149faadce2f57c3702eda,

title = "Circular Convex Bipartite Graphs: Maximum Matching and Hamiltonian Circuits",

abstract = " The maximum matching and its related problems in convex bipartite graphs were studied by Glover (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 arc of A . We present linear time algorithms for finding a maximum matching and a Hamiltonian circuit in circular convex bipartite graphs. ",

keywords = "Algorithms, Circular convex bipartite graph, Convex bipartite graph, Hamiltonian circuit, Maximum matching",

author = "Liang, {Y. Daniel} and Norbert Blum",

note = "The maximum matching and its related problems in convex bipartite graphs were studied by Glover (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.",

year = "1995",

month = nov,

day = "24",

doi = "10.1016/0020-0190(95)00145-3",

language = "American English",

volume = "56",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Circular Convex Bipartite Graphs: Maximum Matching and Hamiltonian Circuits

AU - Liang, Y. Daniel

AU - Blum, Norbert

N1 - The maximum matching and its related problems in convex bipartite graphs were studied by Glover (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.

PY - 1995/11/24

Y1 - 1995/11/24

N2 - The maximum matching and its related problems in convex bipartite graphs were studied by Glover (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 arc of A . We present linear time algorithms for finding a maximum matching and a Hamiltonian circuit in circular convex bipartite graphs.

AB - The maximum matching and its related problems in convex bipartite graphs were studied by Glover (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 arc of A . We present linear time algorithms for finding a maximum matching and a Hamiltonian circuit in circular convex bipartite graphs.

KW - Algorithms

KW - Circular convex bipartite graph

KW - Convex bipartite graph

KW - Hamiltonian circuit

KW - Maximum matching

UR - https://www.sciencedirect.com/science/article/abs/pii/0020019095001453

U2 - 10.1016/0020-0190(95)00145-3

DO - 10.1016/0020-0190(95)00145-3

M3 - Article

SN - 0020-0190

VL - 56

JO - Information Processing Letters

JF - Information Processing Letters

ER -

Circular Convex Bipartite Graphs: Maximum Matching and Hamiltonian Circuits

Abstract

Disciplines

Keywords

Access to Document

Other files and links

Fingerprint

Cite this