Presentation	1999/5/24 The Number of Connected Components in Graphs and Its Applications Ryuhie Uehara,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	For any given graph and an integer k, the number of connected components with k vertices in the graph is investigated. For the vertex set of size n and the maximum degree Δ, the number is bounded above by [numerical formula]. The factor Δ^k is essential, since we give the lower bound n(Δ/29^ for k<(2n)/Δ. We also show that all connected components with k vertices are enumerable in O(m+n/(logΔ)Δ^<2k>) time with O(n+m) space, where m is the number of edges. Thus, if Δ^k is bounded above by some polynomial of n(e. g. Δ is fixed and k=O(log n)), we can check all connected components with k vertices in polynomial time of n. Under the assumption, several intractable problems (including Topological Containment (Subgraph Isomorphism), Small Minimum Degree 4 Subgraph, Bipartite Graph Embedding, Steiner Tree, and k-Minimum Spanning Tree) are put into tractable.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	Graph theory / parameterized complexity / enumeration algorithm.
Paper #	COMP99-10
Date of Issue

Conference Information
Committee	COMP
Conference Date	1999/5/24(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)	The Number of Connected Components in Graphs and Its Applications
Sub Title (in English)
Keyword(1)	Graph theory
Keyword(2)	parameterized complexity
Keyword(3)	enumeration algorithm.
1st Author's Name	Ryuhie Uehara
1st Author's Affiliation	Faculty of Natural Sciences, Komazawa University()
Date	1999/5/24
Paper #	COMP99-10
Volume (vol)	vol.99
Number (no)	86
Page	pp.pp.-
#Pages	8
Date of Issue