Institutional Repository
| Detecting and characterizing small dense bipartite-like subgraphs by the bipartiteness ratio measure | |
| Li, Angsheng (1); Peng, Pan (1) | |
| 2013 | |
| Conference Name | 24th International Symposium on Algorithms and Computation, ISAAC 2013 |
| Pages | 655-665 |
| Conference Date | December 16, 2013 - December 18, 2013 |
| Conference Place | Hong Kong, China |
| Indexed Type | CPCI ; EI |
| Publish Place | Springer Verlag, Tiergartenstrasse 17, Heidelberg, D-69121, Germany |
| ISSN | 3029743 |
| ISBN | 9783642450297 |
| Department | (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 |
| English Abstract | 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 2k1+Ε 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 θ-2 k 1+Ε ln 3 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 2k1+Ε 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 θ-2 k 1+Ε ln 3 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. |
| Language | 英语 |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/16524 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment