Presentation	2003/7/25 Minimum Cost Source Location Problem with Local 3-Vertex-Connectivity Requirements Hitoshi FUJITA, Toshimasa ISHII, Hiroshi NAGAMOCHI,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	Let G= (V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v∈V has a demand d (v)∈Z_+ and a cost c (v)∈R_+, where Z_+ and R_+ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity in a given graph G asks to find a set S of vertices minimizing Σ_ c (v) sucn that there are at least d (v) pairwise vertex-disjoint paths from S to v for each vertex v∈V-S. It is known that if there exists a vertex v∈V with d (v)≧4, then the problem is NP-hard even in the case where every vertex has a uniform cost. In this paper, we show that the problem can be solved in polynomial time.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	graph algorithm / undirected graph / location problem / local vertex-connectivity / polynomial time algorithm
Paper #	COMP2003-33
Date of Issue

Conference Information
Committee	COMP
Conference Date	2003/7/25(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	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Minimum Cost Source Location Problem with Local 3-Vertex-Connectivity Requirements
Sub Title (in English)
Keyword(1)	graph algorithm
Keyword(2)	undirected graph
Keyword(3)	location problem
Keyword(4)	local vertex-connectivity
Keyword(5)	polynomial time algorithm
1st Author's Name	Hitoshi FUJITA
1st Author's Affiliation	Department of Information and Computer Science, Toyohashi University of Technology()
2nd Author's Name	Toshimasa ISHII
2nd Author's Affiliation	Department of Information and Computer Science, Toyohashi University of Technology
3rd Author's Name	Hiroshi NAGAMOCHI
3rd Author's Affiliation	Department of Information and Computer Science, Toyohashi University of Technology
Date	2003/7/25
Paper #	COMP2003-33
Volume (vol)	vol.103
Number (no)	246
Page	pp.pp.-
#Pages	8
Date of Issue