Endre Csóka
Local algorithms with public randomisation on sparse graphs.
Thu, 02/09/2012 - 15:01 — SomNambulAuthors: Endre Csóka
Subjects: Combinatorics
AbstractConsider the problem when we want to construct some structure on a bounded
degree graph, e.g. an almost maximum matching, and we want to decide about each
edge depending only on its constant radius neighbourhood. We show that the
information about the local statistics of the graph does not help here at all.
Namely, if there exists a local algorithm which can use any local statistics
about the graph, and produces a good approximation for a parameter, then there
exists an approximation algorithm not using any statistics.Maximum flow is approximable by deterministic constant-time algorithm in sparse networks.
Wed, 05/05/2010 - 15:01 — SomNambulAuthors: Endre Csóka
Subjects: Data Structures and Algorithms
AbstractWe show a deterministic constant-time parallel algorithm for finding an
almost maximum flow in multisource-multitarget networks with bounded degrees
and bounded edge capacities. As a consequence, we show that the value of the
maximum flow over the number of nodes is a testable parameter on these
networks.
User login
