TY - GEN
T1 - Detecting and characterizing small dense bipartite-like subgraphs by the bipartiteness ratio measure
AU - Li, Angsheng
AU - Peng, Pan
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84893402533
U2 - 10.1007/978-3-642-45030-3_61
DO - 10.1007/978-3-642-45030-3_61
M3 - 会议稿件
AN - SCOPUS:84893402533
SN - 9783642450297
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 655
EP - 665
BT - Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
T2 - 24th International Symposium on Algorithms and Computation, ISAAC 2013
Y2 - 16 December 2013 through 18 December 2013
ER -