Zobrazeno 1 - 10
of 96
pro vyhledávání: '"Reidl, Felix"'
Autor:
Bentert, Matthias, Salomao, Daniel Coimbra, Crane, Alex, Mizutani, Yosuke, Reidl, Felix, Sullivan, Blair D.
We investigate whether algorithms based on arithmetic circuits are a viable alternative to existing solvers for Graph Inspection, a problem with direct application in robotic motion planning. Specifically, we seek to address the high memory usage of
Externí odkaz:
http://arxiv.org/abs/2409.08219
Autor:
Mizutani, Yosuke, Salomao, Daniel Coimbra, Crane, Alex, Bentert, Matthias, Drange, Pål Grønås, Reidl, Felix, Kuntz, Alan, Sullivan, Blair D.
Autonomous robotic inspection, where a robot moves through its environment and inspects points of interest, has applications in industrial settings, structural health monitoring, and medicine. Planning the paths for a robot to safely and efficiently
Externí odkaz:
http://arxiv.org/abs/2407.00251
We explore Cluster Editing and its generalization Correlation Clustering with a new operation called permissive vertex splitting which addresses finding overlapping clusters in the face of uncertain information. We determine that both problems are NP
Externí odkaz:
http://arxiv.org/abs/2402.10335
We show that the VC-dimension of a graph can be computed in time $n^{\log d+1} d^{O(d)}$, where $d$ is the degeneracy of the input graph. The core idea of our algorithm is a data structure to efficiently query the number of vertices that see a specif
Externí odkaz:
http://arxiv.org/abs/2308.08868
A tournament is an orientation of a complete graph. We say that a vertex $x$ in a tournament $\vec T$ controls another vertex $y$ if there exists a directed path of length at most two from $x$ to $y$. A vertex is called a king if it controls every ve
Externí odkaz:
http://arxiv.org/abs/2209.12082
In the classic TARGET SAT SELECTION problem, we are asked to minimise the number of nodes to activate so that, after the application of a certain propagation process, all nodes of the graph are active. Bazgan and Chopin [Discrete Optimization}, 14:17
Externí odkaz:
http://arxiv.org/abs/2111.11834
Autor:
Einarson, Carl, Reidl, Felix
We unify and extend previous kernelization techniques in sparse classes [6,17] by defining water lilies and show how they can be used in bounded expansion classes to construct linear bikernels for (r, c)-Dominating Set, (r, c)-Scattered Set, Total r-
Externí odkaz:
http://arxiv.org/abs/2002.09028
Autor:
Reidl, Felix, Sullivan, Blair D.
We present an algorithm to count the number of occurrences of a pattern graph $H$ as an induced subgraph in a host graph $G$. If $G$ belongs to a bounded expansion class, the algorithm runs in linear time. Our design choices are motivated by the need
Externí odkaz:
http://arxiv.org/abs/2001.05236
Autor:
Einarson, Carl, Reidl, Felix
Inspired by the potential of improving tractability via gap- or above-guarantee parametrisations, we investigate the complexity of Dominating Set when given a suitable lower-bound witness. Concretely, we consider being provided with a maximal r-indep
Externí odkaz:
http://arxiv.org/abs/1906.09180
We prove almost tight bounds on the length of paths in $2$-edge-connected cubic graphs. Concretely, we show that (i) every $2$-edge-connected cubic graph of size $n$ has a path of length $\Omega\left(\frac{\log^2{n}}{\log{\log{n}}}\right)$, and (ii)
Externí odkaz:
http://arxiv.org/abs/1903.02508