Detecting and characterizing small dense bipartite-like subgraphs by the bipartiteness ratio measure

ISCAS OpenIR

	Detecting and characterizing small dense bipartite-like subgraphs by the bipartiteness ratio measure
	Li, Angsheng (1); Peng, Pan (1)
	2013
会议名称	24th International Symposium on Algorithms and Computation, ISAAC 2013
页码	655-665
会议日期	December 16, 2013 - December 18, 2013
会议地点	Hong Kong, China
收录类别	CPCI ; EI
出版地	Springer Verlag, Tiergartenstrasse 17, Heidelberg, D-69121, Germany
ISSN	3029743
ISBN	9783642450297
部门归属	(1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China; (2) Department of Computer Science, Technische Universität Dortmund, Germany
摘要	We study the problem of finding and characterizing subgraphs with small bipartiteness ratio. We give a bicriteria approximation algorithm SwpDB such that if there exists a subset S of volume at most k and bipartiteness ratio θ, then for any 0 < Ε < 1/2, it finds a set S′ of volume at most 2k^1+Ε and bipartiteness ratio at most 4√θ/Ε. By combining a truncation operation, we give a local algorithm LocDB, which has asymptotically the same approximation guarantee as the algorithm SwpDB on both the volume and bipartiteness ratio of the output set, and runs in time O(Ε² θ^-2 k ^1+Ε ln ³ k), independent of the size of the graph. Finally, we give a spectral characterization of the small dense bipartite-like subgraphs by using the kth largest eigenvalue of the Laplacian of the graph. © 2013 Springer-Verlag.; We study the problem of finding and characterizing subgraphs with small bipartiteness ratio. We give a bicriteria approximation algorithm SwpDB such that if there exists a subset S of volume at most k and bipartiteness ratio θ, then for any 0 < Ε < 1/2, it finds a set S′ of volume at most 2k^1+Ε and bipartiteness ratio at most 4√θ/Ε. By combining a truncation operation, we give a local algorithm LocDB, which has asymptotically the same approximation guarantee as the algorithm SwpDB on both the volume and bipartiteness ratio of the output set, and runs in time O(Ε² θ^-2 k ^1+Ε ln ³ k), independent of the size of the graph. Finally, we give a spectral characterization of the small dense bipartite-like subgraphs by using the kth largest eigenvalue of the Laplacian of the graph. © 2013 Springer-Verlag.
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16524
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Li, Angsheng ,Peng, Pan . Detecting and characterizing small dense bipartite-like subgraphs by the bipartiteness ratio measure[C]. Springer Verlag, Tiergartenstrasse 17, Heidelberg, D-69121, Germany,2013:655-665.