Helsinki Algorithms Seminar: "Sinkless orientations, balanced orientations, and balanced splitting" Jukka Suomela, Aalto

Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design.

Jukka Suomela
Assistant Professor, Aalto University

Sinkless orientations, balanced orientations, and balanced splitting

Abstract:

I will discuss graph problems of the following types:

(a) Sinkless orientation: Given a 3-regular graph, find an orientation such that all nodes have outdegree at least 1.

(b) Balanced orientation: Given a (2k+1)-regular graph, find an orientation such that all nodes have outdegree at least k and indegree at least k.

(c) Balanced splitting: Given a (2k+4)-regular graph, colour the edges of the graph red and blue such that each node is incident to at least k red edges and at least k blue edges.

By prior work, we know how to solve (a) efficiently with distributed algorithms. I will show how to use (a) as a black box to solve also (b) and (c) efficiently.

This is joint work with Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, and Jara Uitto; our work received the best paper award in DISC 2017. See here for more information.

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

Welcome!