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

DOI10.1016/0166-218X(93)90052-PzbMath0768.68183OpenAlexW2102127932MaRDI QIDQ1803681

Leen Stougie

Publication date: 29 June 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90052-p

zbMATH Keywords

partitionrandom graphsrandomized extension-rotation algorithm

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item