Zobrazeno 1 - 10
of 719
pro vyhledávání: '"BOSE, PROSENJIT"'
The $d$-independence number of a graph $G$ is the largest possible size of an independent set $I$ in $G$ where each vertex of $I$ has degree at least $d$ in $G$. Upper bounds for the $d$-independence number in planar graphs are well-known for $d=3,4,
Externí odkaz:
http://arxiv.org/abs/2411.02686
Autor:
Aloupis, Greg, Biniaz, Ahmad, Bose, Prosenjit, De Carufel, Jean-Lou, Eppstein, David, Maheshwari, Anil, Odak, Saeed, Smid, Michiel, Tóth, Csaba D., Valtr, Pavel
Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, shortest spa
Externí odkaz:
http://arxiv.org/abs/2410.05580
Cops and Robbers is a type of pursuit-evasion game played on a graph where a set of cops try to capture a single robber. The cops first choose their initial vertex positions, and later the robber chooses a vertex. The cops and robbers make their move
Externí odkaz:
http://arxiv.org/abs/2409.16279
In this article, we present an approximation algorithm for solving the Weighted Region Problem amidst a set of $ n $ non-overlapping weighted disks in the plane. For a given parameter $ \varepsilon \in (0,1]$, the length of the approximate path is at
Externí odkaz:
http://arxiv.org/abs/2409.08869
Autor:
Bekos, Michael A., Bose, Prosenjit, Büngener, Aaron, Dujmović, Vida, Hoffmann, Michael, Kaufmann, Michael, Morin, Pat, Odak, Saeed, Weinberger, Alexandra
We study the impact of forbidding short cycles to the edge density of $k$-planar graphs; a $k$-planar graph is one that can be drawn in the plane with at most $k$ crossings per edge. Specifically, we consider three settings, according to which the fo
Externí odkaz:
http://arxiv.org/abs/2408.16085
The problem of computing vertex and edge connectivity of a graph are classical problems in algorithmic graph theory. The focus of this paper is on computing these parameters on embedded graphs. A typical example of an embedded graph is a planar graph
Externí odkaz:
http://arxiv.org/abs/2407.00586
Continuous 2-dimensional space is often discretized by considering a mesh of weighted cells. In this work we study how well a weighted mesh approximates the space, with respect to shortest paths. We consider a shortest path $ \mathit{SP_w}(s,t) $ fro
Externí odkaz:
http://arxiv.org/abs/2404.07562
We consider the problem of finding a geodesic disc of smallest radius containing at least $k$ points from a set of $n$ points in a simple polygon that has $m$ vertices, $r$ of which are reflex vertices. We refer to such a disc as a SKEG disc. We pres
Externí odkaz:
http://arxiv.org/abs/2402.00336
Autor:
Bose, Prosenjit, Tuttle, Tyler
In this article, we present a construction of a spanner on a set of $n$ points in $\mathbf{R}^d$ that we call a heavy path WSPD spanner. The construction is parameterized by a constant $s > 2$ called the separation ratio. The size of the graph is $O(
Externí odkaz:
http://arxiv.org/abs/2312.15145
Finding the exact spanning ratio of a Delaunay graph has been one of the longstanding open problems in Computational Geometry. Currently there are only four convex shapes for which the exact spanning ratio of their Delaunay graph is known: the equila
Externí odkaz:
http://arxiv.org/abs/2312.14305