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 |
| 会议日期 | December 16, 2013 - December 18, 2013 |
| 会议地点 | Hong Kong, China |
| 页码 | 655-665 |
| 中文摘要 | 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. |
| 收录类别 | CPCI ; EI |
| 会议录出版地 | Springer Verlag, Tiergartenstrasse 17, Heidelberg, D-69121, Germany |
| 语种 | 英语 |
| ISSN号 | 3029743 |
| ISBN号 | 9783642450297 |
| 源URL | [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]. 见:24th International Symposium on Algorithms and Computation, ISAAC 2013. Hong Kong, China. December 16, 2013 - December 18, 2013. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。