Zobrazeno 1 - 10
of 105
pro vyhledávání: '"Husfeldt, Thore"'
Autor:
Björklund, Andreas, Husfeldt, Thore
We consider the parameterised $k,e$-Long Cycle problem, in which you are given an $n$-vertex undirected graph $G$, a specified edge $e$ in $G$, and a positive integer $k$, and are asked to decide if the graph $G$ has a simple cycle through $e$ of len
Externí odkaz:
http://arxiv.org/abs/2408.03699
In this paper we further explore the recently discovered connection by Bj\"{o}rklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Progr. Math. 1994] and the three-way partitioning problem. We show th
Externí odkaz:
http://arxiv.org/abs/2404.04987
Given a directed graph, we show how to efficiently find a shortest (directed, simple) cycle on an even number of vertices. As far as we know, no polynomial-time algorithm was previously known for this problem. In fact, finding any even cycle in a dir
Externí odkaz:
http://arxiv.org/abs/2111.02992
We systematically investigate the complexity of counting subgraph patterns modulo fixed integers. For example, it is known that the parity of the number of $k$-matchings can be determined in polynomial time by a simple reduction to the determinant. W
Externí odkaz:
http://arxiv.org/abs/2107.00629
Autor:
Björklund, Andreas, Husfeldt, Thore
Given an undirected graph and two disjoint vertex pairs $s_1,t_1$ and $s_2,t_2$, the Shortest two disjoint paths problem (S2DP) asks for the minimum total length of two vertex disjoint paths connecting $s_1$ with $t_1$, and $s_2$ with $t_2$, respecti
Externí odkaz:
http://arxiv.org/abs/1806.07586
We show that the eccentricities, diameter, radius, and Wiener index of an undirected $n$-vertex graph with nonnegative edge lengths can be computed in time $O(n\cdot \binom{k+\lceil\log n\rceil}{k} \cdot 2^k k^2 \log n)$, where $k$ is the treewidth o
Externí odkaz:
http://arxiv.org/abs/1805.07135
We devise an algorithm that approximately computes the number of paths of length $k$ in a given directed graph with $n$ vertices up to a multiplicative error of $1 \pm \varepsilon$. Our algorithm runs in time $\varepsilon^{-2} 4^k(n+m) \operatorname{
Externí odkaz:
http://arxiv.org/abs/1804.09448
Autor:
Husfeldt, Thore
This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aim
Externí odkaz:
http://arxiv.org/abs/1505.05825
Autor:
Björklund, Andreas, Husfeldt, Thore
We present a deterministic algorithm that given any directed graph on n vertices computes the parity of its number of Hamiltonian cycles in O(1.619^n) time and polynomial space. For bipartite graphs, we give a 1.5^n poly(n) expected time algorithm. O
Externí odkaz:
http://arxiv.org/abs/1301.7250
Publikováno v:
ACM Trans. Algorithms 10(4): 21:1-21:32 (2014)
We show conditional lower bounds for well-studied #P-hard problems: (a) The number of satisfying assignments of a 2-CNF formula with n variables cannot be counted in time exp(o(n)), and the same is true for computing the number of all independent set
Externí odkaz:
http://arxiv.org/abs/1206.1775