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

DOI10.1016/0166-218X(93)90052-PMaRDI QIDQ1803681zbMATH OpenOpenAlexFDO

Authors L. 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

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

Recommendations

• scientific article; zbMATH DE number 3855167
• Efficient algorithms for path partitions
• An exact algorithm for graph partitioning
• scientific article; zbMATH DE number 3855168
• Efficient algorithms for some path partitioning problems
• Partitioning graphs into paths or cycles of prescribed lengths
• On the path partition of graphs
• A linear time algorithm for graph partition problems
• Partitioning a graph into vertex-disjoint paths

Cites work

• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3902655 (Why is no real title available?)
• scientific article; zbMATH DE number 3930719 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)

Cited in

(2)

• A note on the partitioning shortest path algorithm
• Splitting an Expander Graph

This page was built for publication: A fast randomized algorithm for partitioning a graph into paths of fixed length

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1803681)