Presentation	1994/11/17 Constructing a Bipartite Graph of Maximum Connectivity with Prescribed Degrees Takao Asano,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	A pair of nonnegative integer sequences {D_1, D_2} with (D_1=(d_<1, 1>, d_<1, 2>…, d_<1, n1>) and D_2=(d_<2, 1>, …d_<2, 2>…, d_<2, n2>) is a bipartite graphical sequence, if there is a bipartite graph G with degrees {D_1, D_2} (i.e., G has two independent vertex sets V_1={v_<1, 1>, v_<1, 2>, …, v_<1, n1>} and V_2={v_<2, 1>, v_<2, 2>, …, v_<2, n2> } such that d_ is the degree of vertex v_ of G for each i=1, 2 and ji=1, 2, …, ni). The connectivity κ({D_1, D_2}) of a bipartite graphical sequence {D_1, D_2} is defined to be the maximum integer k such that there is a k-connected bipartite graph with degrees {D_1, D_2}. In this paper, we present a characterization of a k-connected bipartite graphical sequence. Based on this characterization, we can obtain an O(nlog logn) time algorithm, for a given bipartite graphical sequence {D_1, D_2}, to construct a κ({D_1, D_2})-connected bipartite graph with degrees {D_1, D_2} (n=n1+n2).
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	bipartite graph / connectivity / degree sequence / implicitly represented graph
Paper #	CAS94-64,CST94-24
Date of Issue

Conference Information
Committee	CST
Conference Date	1994/11/17(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Concurrent System Technology (CST)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Constructing a Bipartite Graph of Maximum Connectivity with Prescribed Degrees
Sub Title (in English)
Keyword(1)	bipartite graph
Keyword(2)	connectivity
Keyword(3)	degree sequence
Keyword(4)	implicitly represented graph
1st Author's Name	Takao Asano
1st Author's Affiliation	Department of Information and System Engineering Chuo University()
Date	1994/11/17
Paper #	CAS94-64,CST94-24
Volume (vol)	vol.94
Number (no)	333
Page	pp.pp.-
#Pages	8
Date of Issue