Doemoetoer Palvoelgyi

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

We study two decomposition problems in combinatorial geometry. The first part of the thesis deals with the decomposition of multiple coverings of the plane. We say that a planar set is cover-decomposable if there is a constant m such that any m-fold coveri ...

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...

A system of sets forms an m-fold covering of a set X if every point of X belongs to at least m of its members. A 1-fold covering is called a covering. The problem of splitting multiple coverings into several coverings was motivated by classical density est ...

We consider the problem of testing whether the maximum integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomi ...

Tucker's lemma states that if we triangulate the unit disc centered at the origin and color the vertices with {1, 1,2, 2} in an antipodal way (if vertical bar z vertical bar = 1, then the sum of the colors of z and -z is zero), then there must be an edge F ...

We introduce a novel and general approach for digitalization of line segments in the plane that satisfies a set of axioms naturally arising from Euclidean axioms. In particular, we show how to derive such a system of digital segments from any total order o ...

For an integer d a parts per thousand yen 1, let tau(d) be the smallest integer with the following property: if v (1), v (2), . . . , v (t) is a sequence of t a parts per thousand yen 2 vectors in [-1, 1] (d) with , then there is a set of indices, 2 a part ...

We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different sl ...

We show that for any concave polygon that has no parallel sides and for any k, there is a k-fold covering of some point set by the translates of this polygon that cannot be decomposed into two coverings. Moreover, we give a complete classification of open ...

We introduce the Turan problem for edge ordered graphs. We call a simple graph edge ordered, if its edges are linearly ordered. An isomorphism between edge ordered graphs must respect the edge order. A subgraph of an edge ordered graph is itself an edge or ...

Given a graph G, an obstacle representation of G is a set of points in the plane representing the vertices of G, together with a set of connected obstacles such that two vertices of G are joined by an edge if and only if the corresponding points can be con ...

We show that for any open convex polygon P, there is a constant k(P) such that any k(P)-fold covering of the plane with translates of P can be decomposed into two coverings. ...

A well studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxati ...

We give a new, combinatorial proof for the necklace splitting problem for two thieves using only Tucker's lemma (a combinatorial version of the Borsuk-Ulam theorem). We show how this method can be applied to obtain a related recent result of Simonyi and ev ...

A general (rectangular) partition is a partition of a rectangle into an arbitrary number of non-overlapping subrectangles. This paper examines vertex 4-colorings of general partitions where every subrectangle is required to have all four colors appear on i ...

Doemoetoer Palvoelgyi

Chat with Graph Search

Decomposition of Geometric Set Systems and Graphs

Adaptive majority problems for restricted query graphs and for weighted sets

Unsplittable coverings in the plane

Testing additive integrality gaps

Adaptive Majority Problems For Restricted Query Graphs And For Weighted Sets

2D-TUCKER Is PPAD-Complete

Consistent Digital Line Segments

Vectors in a box

Drawing planar graphs of bounded degree with few slopes

Indecomposable Coverings with Concave Polygons

Drawing Planar Graphs Of Bounded Degree With Few Slopes

Edge Ordered Turan Problems

Lower bounds on the obstacle number of graphs

Convex polygons are cover-decomposable

Unsplittable Coverings in the Plane

Bin Packing via Discrepancy of Permutations

Combinatorial necklace splitting

Permutations, hyperplanes and polynomials over finite fields

Polychromatic colorings of arbitrary rectangular partitions

Consistent digital line segments