A fast randomized algorithm for partitioning a graph into paths of fixed length

L. Stougie

doi:10.1016/0166-218X(93)90052-P

A fast randomized algorithm for partitioning a graph into paths of fixed length

L. Stougie

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

Abstract

A randomized extension-rotation algorithm is presented to partition an undirected graph G=(V,E) into vertex disjoint paths of fixed length. In O(|V|log|V|) time it finds such a partition if one exists with high probability, when applied to random graphs with sufficiently high edge density.

Original language	English
Pages (from-to)	291-303
Journal	Discrete Applied Mathematics
Volume	42
Issue number	2-3
DOIs	https://doi.org/10.1016/0166-218X(93)90052-P
Publication status	Published - 1993

Access to Document

10.1016/0166-218X(93)90052-P

Cite this

@article{7bfd328456b948578d731091388c2bb0,

title = "A fast randomized algorithm for partitioning a graph into paths of fixed length",

abstract = "A randomized extension-rotation algorithm is presented to partition an undirected graph G=(V,E) into vertex disjoint paths of fixed length. In O(|V|log|V|) time it finds such a partition if one exists with high probability, when applied to random graphs with sufficiently high edge density.",

author = "L. Stougie",

year = "1993",

doi = "10.1016/0166-218X(93)90052-P",

language = "English",

volume = "42",

pages = "291--303",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "2-3",

}

TY - JOUR

T1 - A fast randomized algorithm for partitioning a graph into paths of fixed length

AU - Stougie, L.

PY - 1993

Y1 - 1993

N2 - A randomized extension-rotation algorithm is presented to partition an undirected graph G=(V,E) into vertex disjoint paths of fixed length. In O(|V|log|V|) time it finds such a partition if one exists with high probability, when applied to random graphs with sufficiently high edge density.

AB - A randomized extension-rotation algorithm is presented to partition an undirected graph G=(V,E) into vertex disjoint paths of fixed length. In O(|V|log|V|) time it finds such a partition if one exists with high probability, when applied to random graphs with sufficiently high edge density.

U2 - 10.1016/0166-218X(93)90052-P

DO - 10.1016/0166-218X(93)90052-P

M3 - Article

SN - 0166-218X

VL - 42

SP - 291

EP - 303

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 2-3

ER -

A fast randomized algorithm for partitioning a graph into paths of fixed length

Abstract

Access to Document

Fingerprint

Cite this