An approximation algorithm for clustering graphs with dominating diametral path

Jitender S. Deogun; Dieter Kratsch; George Steiner

doi:10.1016/s0020-0190(97)81663-8

An approximation algorithm for clustering graphs with dominating diametral path

Jitender S. Deogun, Dieter Kratsch, George Steiner

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

26 Scopus citations

Abstract

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 a k-clustering for graphs having a dominating diametral path.

Original language	English (US)
Pages (from-to)	121-127
Number of pages	7
Journal	Information Processing Letters
Volume	61
Issue number	3
DOIs	https://doi.org/10.1016/s0020-0190(97)81663-8
State	Published - Feb 14 1997

Keywords

Approximation algorithms
Design of algorithms
Graph clustering
Special graph classes

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/s0020-0190(97)81663-8

Cite this

@article{3e1234085d4f444585229177644751e4,

title = "An approximation algorithm for clustering graphs with dominating diametral path",

abstract = "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 a k-clustering for graphs having a dominating diametral path.",

keywords = "Approximation algorithms, Design of algorithms, Graph clustering, Special graph classes",

author = "Deogun, {Jitender S.} and Dieter Kratsch and George Steiner",

note = "Funding Information: * Corresponding author, Email: steiner@mcmaster.ca. {\textquoteright} This research was suppotted in part by the Office of Naval Research under Grant No. NOOl4-91-J-1693, by the Natural Sciences and Engineering Research Council of Canada under Grant No. OGFO001798 and by Deutsche Forschungsgemeinschaft under Rr 1371/1-l.",

year = "1997",

month = feb,

day = "14",

doi = "10.1016/s0020-0190(97)81663-8",

language = "English (US)",

volume = "61",

pages = "121--127",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - An approximation algorithm for clustering graphs with dominating diametral path

AU - Deogun, Jitender S.

AU - Kratsch, Dieter

AU - Steiner, George

N1 - Funding Information: * Corresponding author, Email: steiner@mcmaster.ca. ’ This research was suppotted in part by the Office of Naval Research under Grant No. NOOl4-91-J-1693, by the Natural Sciences and Engineering Research Council of Canada under Grant No. OGFO001798 and by Deutsche Forschungsgemeinschaft under Rr 1371/1-l.

PY - 1997/2/14

Y1 - 1997/2/14

N2 - 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 a k-clustering for graphs having a dominating diametral path.

AB - 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 a k-clustering for graphs having a dominating diametral path.

KW - Approximation algorithms

KW - Design of algorithms

KW - Graph clustering

KW - Special graph classes

UR - http://www.scopus.com/inward/record.url?scp=0043223515&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0043223515&partnerID=8YFLogxK

U2 - 10.1016/s0020-0190(97)81663-8

DO - 10.1016/s0020-0190(97)81663-8

M3 - Article

AN - SCOPUS:0043223515

SN - 0020-0190

VL - 61

SP - 121

EP - 127

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

An approximation algorithm for clustering graphs with dominating diametral path

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this