Decomposition by clique separators

Robert E. Tarjan

doi:10.1016/0012-365X(85)90051-2

Decomposition by clique separators

Robert E. Tarjan

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

314 Scopus citations

Abstract

We consider the problem of decomposing a graph by means of clique separators, by which we mean finding cliques (complete graphs) whose removal disconnects the graph. We give an O(nm)-time algorithm for finding a decomposition of an n-vertex, m-edge graph. We describe how such a decomposition can be used in divide-and-conquer algorithms for various graph problems, such as graph coloring and finding maximum independent sets. We survey classes of graphs for which such divide-and-conquer algorithms are especially useful.

Original language	English (US)
Pages (from-to)	221-232
Number of pages	12
Journal	Discrete Mathematics
Volume	55
Issue number	2
DOIs	https://doi.org/10.1016/0012-365X(85)90051-2
State	Published - Jul 1985
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(85)90051-2

Cite this

@article{55fbd3a955ab4e78a1707e77989a5258,

title = "Decomposition by clique separators",

abstract = "We consider the problem of decomposing a graph by means of clique separators, by which we mean finding cliques (complete graphs) whose removal disconnects the graph. We give an O(nm)-time algorithm for finding a decomposition of an n-vertex, m-edge graph. We describe how such a decomposition can be used in divide-and-conquer algorithms for various graph problems, such as graph coloring and finding maximum independent sets. We survey classes of graphs for which such divide-and-conquer algorithms are especially useful.",

author = "Tarjan, {Robert E.}",

year = "1985",

month = jul,

doi = "10.1016/0012-365X(85)90051-2",

language = "English (US)",

volume = "55",

pages = "221--232",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Decomposition by clique separators

AU - Tarjan, Robert E.

PY - 1985/7

Y1 - 1985/7

N2 - We consider the problem of decomposing a graph by means of clique separators, by which we mean finding cliques (complete graphs) whose removal disconnects the graph. We give an O(nm)-time algorithm for finding a decomposition of an n-vertex, m-edge graph. We describe how such a decomposition can be used in divide-and-conquer algorithms for various graph problems, such as graph coloring and finding maximum independent sets. We survey classes of graphs for which such divide-and-conquer algorithms are especially useful.

AB - We consider the problem of decomposing a graph by means of clique separators, by which we mean finding cliques (complete graphs) whose removal disconnects the graph. We give an O(nm)-time algorithm for finding a decomposition of an n-vertex, m-edge graph. We describe how such a decomposition can be used in divide-and-conquer algorithms for various graph problems, such as graph coloring and finding maximum independent sets. We survey classes of graphs for which such divide-and-conquer algorithms are especially useful.

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

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

U2 - 10.1016/0012-365X(85)90051-2

DO - 10.1016/0012-365X(85)90051-2

M3 - Article

AN - SCOPUS:0000455611

SN - 0012-365X

VL - 55

SP - 221

EP - 232

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

Decomposition by clique separators

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this