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

L. Stougie

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer 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-2Engels
    Pagina's (van-tot)291-303
    TijdschriftDiscrete Applied Mathematics
    Volume42
    Nummer van het tijdschrift2-3
    DOI's
    StatusGepubliceerd - 1993

    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