An approximation algorithm for clustering graphs with dominating diametral path

被引：24

作者：

Deogun, JS

Kratsch, D

Steiner, G

机构：

[1] MCMASTER UNIV, MANAGEMENT SCI & INFORMAT SYST AREA, HAMILTON, ON L8S 4M4, CANADA

[2] UNIV NEBRASKA, DEPT COMP SCI & ENGN, LINCOLN, NE 68588 USA

[3] UNIV JENA, FAK MATH & INFORMAT, D-07740 JENA, GERMANY

来源：

INFORMATION PROCESSING LETTERS | 1997年 / 61卷 / 03期

关键词：

design of algorithms; approximation algorithms; graph clustering; special graph classes;

D O I：

10.1016/S0020-0190(97)81663-8

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The algorithmic complexity of the graph clustering problem when restricted to special classes of graphs is investigated. We develop results showing the intractability of graph clustering and the hardness of approximating minimum graph clusterings. Our main result is a polynomial time approximation algorithm of constant worst case ratio (at most 3) which computes ak-clustering for graphs having a dominating diametral path. (C) 1997 Published by Elsevier Science B.V.

引用

页码：121 / 127

页数：7

共 22 条

[1]

ABBAS N, 1995, THESIS U ALBERTA EDM

[2]

ABBAS N, 1995, UNPUB CLUSTERING PER

[3]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[4]

BRANDSTADT A, 1991, SMDU199 U DUISB

[5]

Brucker P., 1978, LECTURE NOTES EC MAT, V157, P45

[6]

CORNEIL DG, 1995, P 22 INT C AUT LANG, V944, P292

[7]

Deogun JS, 1995, LECT NOTES COMPUT SC, V1017, P344

[8]

DEOGUN JS, 1984, ACM T DATABASE SYST, V39, P646

[9] CHARACTERIZATIONS OF STRONGLY CHORDAL GRAPHS [J].

FARBER, M .

DISCRETE MATHEMATICS, 1983, 43 (2-3) :173-189

[10]

FARBER M, 1983, DISCRETE APPL MATH, V43, P115

← 1 2 3 →