Grzegorz Guśpiel

most citedComplexity of Finding Perfect Bipartite Matchings Minimizing the Number of Intersecting Edges

1 citations · 1 across the 1 of their papers we have counts for

collaborators

3 papers

cs.DS2019

An in-place, subquadratic algorithm for permutation inversion

Grzegorz Guśpiel

We assume the permutation $π$ is given by an $n$ -element array in which the $i$ -th element denotes the value $π (i)$ . Constructing its inverse in-place (i.e. using $O (lo g n)$ bits…

cs.CC2017★ 1 cited

Complexity of Finding Perfect Bipartite Matchings Minimizing the Number of Intersecting Edges

Grzegorz Guśpiel

Consider a problem where we are given a bipartite graph H with vertices arranged on two horizontal lines in the plane, such that the two sets of vertices placed on the two lines fo…

math.CO2017

On an extremal problem for poset dimension

Grzegorz Guśpiel, Piotr Micek, Adam Polak

Let $f (n)$ be the largest integer such that every poset on $n$ elements has a $2$ -dimensional subposet on $f (n)$ elements. What is the asymptotics of $f (n)$ ? It is easy to see that…