Zobrazeno 1 - 10
of 265
pro vyhledávání: '"ERICKSON, JEFF"'
Deterministic and nondeterministic finite automata (DFAs and NFAs) are abstract models of computation commonly taught in introductory computing theory courses. These models have important applications (such as fast regular expression matching), and a
Externí odkaz:
http://arxiv.org/abs/2405.01717
Autor:
Bastide, Paul, Cook, Linda, Erickson, Jeff, Groenland, Carla, van Kreveld, Marc, Mannens, Isja, Vermeulen, Jordi L.
We introduce a new model of indeterminacy in graphs: instead of specifying all the edges of the graph, the input contains all triples of vertices that form a connected subgraph. In general, different (labelled) graphs may have the same set of connect
Externí odkaz:
http://arxiv.org/abs/2303.06609
Autor:
Erickson, Jeff, Lin, Patrick
We present simpler algorithms for two closely related morphing problems, both based on the barycentric interpolation paradigm introduced by Floater and Gotsman, which is in turn based on Floater's asymmetric extension of Tutte's classical spring-embe
Externí odkaz:
http://arxiv.org/abs/2106.14086
Autor:
Abrahamsen, Mikkel, Erickson, Jeff, Kostitsyna, Irina, Löffler, Maarten, Miltzow, Tillmann, Urhausen, Jérôme, Vermeulen, Jordi, Viglietta, Giovanni
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others' work on beacon-based routing. Consider a human and a puppy on a simple closed curve in the plane. The human can walk along the curve at bounded speed and
Externí odkaz:
http://arxiv.org/abs/2103.09811
We present the first algorithm to morph graphs on the torus. Given two isotopic essentially 3-connected embeddings of the same graph on the Euclidean flat torus, where the edges in both drawings are geodesics, our algorithm computes a continuous defo
Externí odkaz:
http://arxiv.org/abs/2007.07927
Publikováno v:
Logical Methods in Computer Science, Volume 18, Issue 3 (July 28, 2022) lmcs:8555
Inspired by a mathematical riddle involving fuses, we define the "fusible numbers" as follows: $0$ is fusible, and whenever $x,y$ are fusible with $|y-x|<1$, the number $(x+y+1)/2$ is also fusible. We prove that the set of fusible numbers, ordered by
Externí odkaz:
http://arxiv.org/abs/2003.14342
Autor:
Erickson, Jeff, Lin, Patrick
We consider three classes of geodesic embeddings of graphs on Euclidean flat tori: (1) A toroidal graph embedding $\Gamma$ is positive equilibrium if it is possible to place positive weights on the edges, such that the weighted edge vectors incident
Externí odkaz:
http://arxiv.org/abs/2003.10057
We study algorithmic problems that belong to the complexity class of the existential theory of the reals (ER). A problem is ER-complete if it is as hard as the problem ETR and if it can be written as an ETR formula. Traditionally, these problems are
Externí odkaz:
http://arxiv.org/abs/1912.02278
We describe algorithms to efficiently compute minimum $(s,t)$-cuts and global minimum cuts of undirected surface-embedded graphs. Given an edge-weighted undirected graph $G$ with $n$ vertices embedded on an orientable surface of genus $g$, our algori
Externí odkaz:
http://arxiv.org/abs/1910.04278
Autor:
Erickson, Jeff
We prove that the following problem has the same computational complexity as the existential theory of the reals: Given a generic self-intersecting closed curve $\gamma$ in the plane and an integer $m$, is there a polygon with $m$ vertices that is is
Externí odkaz:
http://arxiv.org/abs/1908.09400