Efficient algorithms for the 2-gathering problem

DOI10.1145/1721837.1721850MaRDI QIDQ2930311zbMATH OpenOpenAlexWikidataFDO

Authors Alon Shalita, Uri Zwick, Alon Shalita

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1721837.1721850

zbMATH Keywords

2-gatheringsaugmenting pathsnonbipartite matchings

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Efficient algorithms for the 2-gathering problem
• Optimal pebble motion on a tree
• Multi-color pebble motion on graphs
• A linear-time algorithm for the feasibility of pebble motion on trees
• A linear time algorithm for the \(r\)-gathering problem on the line (extended abstract)

Cited in

(2)

• Efficient algorithms for the 2-gathering problem
• Clustering with lower-bounded sizes. A general graph-theoretic framework

This page was built for publication: Efficient algorithms for the 2-gathering problem

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