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

    Research output: Contribution to JournalArticleAcademicpeer-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 languageEnglish
    Pages (from-to)291-303
    JournalDiscrete Applied Mathematics
    Volume42
    Issue number2-3
    DOIs
    Publication statusPublished - 1993

    Bibliographical note

    0768.68183

    Fingerprint

    Dive into the research topics of 'A fast randomized algorithm for partitioning a graph into paths of fixed length'. Together they form a unique fingerprint.

    Cite this