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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	291-303
Tijdschrift	Discrete Applied Mathematics
Volume	42
Nummer van het tijdschrift	2-3
DOI's	https://doi.org/10.1016/0166-218X(93)90052-P
Status	Gepubliceerd - 1993

Toegang tot document

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

Vingerafdruk Duik in de onderzoeksthema's van 'A fast randomized algorithm for partitioning a graph into paths of fixed length'. Samen vormen ze een unieke vingerafdruk.

Citeer dit

@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",

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

VL - 42

SP - 291

EP - 303

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 2-3

ER -