Advertisement
Published in:
2013 | OriginalPaper | Chapter
Detecting and Characterizing Small Dense Bipartite-Like Subgraphs by the Bipartiteness Ratio Measure
Authors : Angsheng Li, Pan Peng
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 2
k
1 +
ε
and bipartiteness ratio at most
$4\sqrt{\theta/\epsilon}$
. 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
k
th
largest
eigenvalue of the Laplacian of the graph.