Zobrazeno 1 - 10
of 256
pro vyhledávání: '"Ganian, Robert"'
Autor:
Da Lozzo, Giordano, Ganian, Robert, Gupta, Siddharth, Mohar, Bojan, Ordyniak, Sebastian, Zehavi, Meirav
We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an $n$-vertex planar graph whose vertices are partitioned into independent sets (called clusters) with paths - one for each cluster - that connect all the vertice
Externí odkaz:
http://arxiv.org/abs/2409.19410
An $\ell$-page stack layout (also known as an $\ell$-page book embedding) of a graph is a linear order of the vertex set together with a partition of the edge set into $\ell$ stacks (or pages), such that the endpoints of no two edges on the same stac
Externí odkaz:
http://arxiv.org/abs/2409.02833
The approximate computation of twin-width has attracted significant attention already since the moment the parameter was introduced. A recently proposed approach (STACS 2024) towards obtaining a better understanding of this question is to consider th
Externí odkaz:
http://arxiv.org/abs/2407.15514
Several works have recently investigated the parameterized complexity of data completion problems, motivated by their applications in machine learning, and clustering in particular. Interestingly, these problems can be equivalently formulated as clas
Externí odkaz:
http://arxiv.org/abs/2407.10699
A crucial challenge arising in the design of large-scale logistical networks is to optimize parcel sortation for routing. We study this problem under the recent graph-theoretic formalization of Van Dyk, Klause, Koenemann and Megow (IPCO 2024). The pr
Externí odkaz:
http://arxiv.org/abs/2404.16741
We study the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of $k$ robots to their destinations with the aim of minimizing the total ener
Externí odkaz:
http://arxiv.org/abs/2404.15950
A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into pages, which are half-planes bounded by that line. Two-page book embeddings, i.e., book embeddings into 2 pages, are o
Externí odkaz:
http://arxiv.org/abs/2404.14087
We study the complexity-theoretic boundaries of tractability for three classical problems in the context of Hierarchical Task Network Planning: the validation of a provided plan, whether an executable plan exists, and whether a given state can be rea
Externí odkaz:
http://arxiv.org/abs/2401.14174
Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price of anarchy for such games as we
Externí odkaz:
http://arxiv.org/abs/2312.10219
Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function $u$ that took into account distances in a given social network. In this paper, w
Externí odkaz:
http://arxiv.org/abs/2312.07632