A shifting algorithm for continuous tree partitioning

Ronald Becker; Bruno Simeone; Yen I. Chiang

doi:10.1016/S0304-3975(01)00075-5

A shifting algorithm for continuous tree partitioning

Ronald Becker
, Bruno Simeone^*
, Yen I. Chiang

^*Corresponding author for this work

University of Cape Town
University of Rome La Sapienza

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

8 Scopus citations

Abstract

A shifting algorithm for continuous tree partitioning was presented. The polynomial complexity of the algorithm was established and the order of complexity of different computations required by an algorithm were summarized. Results showed that the running time of the continuous shifting algorithm was O(n² p²+n p³) and the algorithm was strongly polynomial.

Original language	English
Pages (from-to)	353-380
Number of pages	28
Journal	Theoretical Computer Science
Volume	282
Issue number	2
DOIs	https://doi.org/10.1016/S0304-3975(01)00075-5
State	Published - 10 06 2002
Externally published	Yes

Keywords

Continuous partitioning
Graph partitioning
Optimization on trees
Tree partitioning

Access to Document

10.1016/S0304-3975(01)00075-5

Cite this

@article{be6d1ad1a30b4fb4a55d9102d81f4f23,

title = "A shifting algorithm for continuous tree partitioning",

abstract = "A shifting algorithm for continuous tree partitioning was presented. The polynomial complexity of the algorithm was established and the order of complexity of different computations required by an algorithm were summarized. Results showed that the running time of the continuous shifting algorithm was O(n2 p2+n p3) and the algorithm was strongly polynomial.",

keywords = "Continuous partitioning, Graph partitioning, Optimization on trees, Tree partitioning",

author = "Ronald Becker and Bruno Simeone and Chiang, \{Yen I.\}",

year = "2002",

month = jun,

day = "10",

doi = "10.1016/S0304-3975(01)00075-5",

language = "英语",

volume = "282",

pages = "353--380",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - A shifting algorithm for continuous tree partitioning

AU - Becker, Ronald

AU - Simeone, Bruno

AU - Chiang, Yen I.

PY - 2002/6/10

Y1 - 2002/6/10

N2 - A shifting algorithm for continuous tree partitioning was presented. The polynomial complexity of the algorithm was established and the order of complexity of different computations required by an algorithm were summarized. Results showed that the running time of the continuous shifting algorithm was O(n2 p2+n p3) and the algorithm was strongly polynomial.

AB - A shifting algorithm for continuous tree partitioning was presented. The polynomial complexity of the algorithm was established and the order of complexity of different computations required by an algorithm were summarized. Results showed that the running time of the continuous shifting algorithm was O(n2 p2+n p3) and the algorithm was strongly polynomial.

KW - Continuous partitioning

KW - Graph partitioning

KW - Optimization on trees

KW - Tree partitioning

UR - https://www.scopus.com/pages/publications/0037054320

U2 - 10.1016/S0304-3975(01)00075-5

DO - 10.1016/S0304-3975(01)00075-5

M3 - 文章

AN - SCOPUS:0037054320

SN - 0304-3975

VL - 282

SP - 353

EP - 380

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2

ER -

A shifting algorithm for continuous tree partitioning

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this