Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
On Editing Graphs into 2-Club Clusters
verfasst von : Hong Liu, Peng Zhang, Daming Zhu
Erschienen in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
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
In this paper, we introduce and study three graph modification problems:
2-Club Cluster Vertex Deletion
,
2-Club Cluster Edge Deletion
, and
2-Club Cluster Editing
. In
2-Club Cluster Vertex Deletion
(
2-Club Cluster Edge Deletion
, and
2-Club Cluster Editing
), one is given an undirected graph
G
and an integer
k
≥ 0, and needs to decide whether it is possible to transform
G
into a 2-club cluster graph by deleting at most
k
vertices (by deleting at most
k
edges, and by deleting and adding totally at most
k
edges). Here, a 2-club cluster graph is a graph in which every connected component is of diameter 2. We first prove that all these three problems are NP-complete. Then, we present for
2-Club Cluster Vertex Deletion
a fixed parameter algorithm with running time
O
∗
(3.31
k
), and for
2-Club Cluster Edge Deletion
a fixed parameter algorithm with running time
O
∗
(2.74
k
).