Browsing by Author "Rotenberg, Eva"

Now showing 1 - 2 of 2

Brief Announcement: Local Advice and Local Decompression
(2024-06-17) Balliu, Alkida; Brandt, Sebastian; Kuhn, Fabian; Nowicki, Krzysztof; Olivetti, Dennis; Rotenberg, Eva; Suomela, Jukka
A4 Artikkeli konferenssijulkaisussa
In this work we study local computation with advice: the goal is to solve a graph problem Π with a distributed algorithm in f (Δ) communication rounds, for some function f that only depends on the maximum degree Δ of the graph, and the key question is how many bits of advice per node are needed. Our main results are: (1) Any locally checkable labeling problem (LCL) can be solved in graphs with sub-exponential growth with only 1 bit of advice per node. Moreover, we can make the set of nodes that carry advice bits arbitrarily sparse. (2) The assumption of sub-exponential growth is necessary: assuming the Exponential-Time Hypothesis (ETH), there are LCLs that cannot be solved in general with any constant number of bits per node. (3) In any graph we can find an almost-balanced orientation (indegrees and outdegrees differ by at most one) with 1 bit of advice per node, and again we can make the advice arbitrarily sparse. (4) As a corollary, we can also compress an arbitrary subset of edges so that a node of degree d stores only d/2 + 2 bits, and we can decompress it locally, in f(Δ) rounds. (5) In any graph of maximum degree Δ, we can find a Δ-coloring (if it exists) with 1 bit of advice per node, and again, we can make the advice arbitrarily sparse. (6) In any 3-colorable graph, we can find a 3-coloring with 1 bit of advice per node. Here, it remains open whether we can make the advice arbitrarily sparse.
Computing Smallest Convex Intersecting Polygons
(2022-09-01) Antoniadis, Antonios; De Berg, Mark; Kisfaludi-Bak, Sándor; Skarlatos, Antonis
A4 Artikkeli konferenssijulkaisussa
A polygon C is an intersecting polygon for a set O of objects in R2 if C intersects each object in O, where the polygon includes its interior. We study the problem of computing the minimum-perimeter intersecting polygon and the minimum-area convex intersecting polygon for a given set O of objects. We present an FPTAS for both problems for the case where O is a set of possibly intersecting convex polygons in the plane of total complexity n. Furthermore, we present an exact polynomial-time algorithm for the minimum-perimeter intersecting polygon for the case where O is a set of n possibly intersecting segments in the plane. So far, polynomial-time exact algorithms were only known for the minimum perimeter intersecting polygon of lines or of disjoint segments.