Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Detecting and Characterizing Small Dense Bipartite-Like Subgraphs by the Bipartiteness Ratio Measure
verfasst von : Angsheng Li, Pan Peng
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.