אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

The dual of a planar graph G is a planar graph G* that has a vertex for each face of G and an edge for each pair of adjacent faces of G. The profound relationship between G and G* is an algorithmic basis for solving numerous (centralized) classical problems on planar graphs. In the standard distributed CONGEST model however, the use of planar duality is very restricted.

We extend the distributed algorithmic toolkit to work on G*, facilitating various algorithms for classical problems on G. E.g., state-of-the-art algorithms for Maximum st-Flow and Undirected Minimum Weight Cycle.

Based on a joint work with Michal Dory, Merav Parter and Oren Weimann.