Results 21 to 30 of about 1,275,858 (359)
Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time [PDF]
TheoretiCS, 2023 Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a randomized Las Vegas dynamic connectivity data structure with $O(\log n(\log\log n)^2)$ amortized expected update time and $O(\log n/\log\log\log n ...
Shang-En Huang +4 more
doaj +1 more source
Defective Coloring on Classes of Perfect Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 In Defective Coloring we are given a graph $G$ and two integers $\chi_d$, $\Delta^*$ and are asked if we can $\chi_d$-color $G$ so that the maximum degree induced by any color class is at most $\Delta^*$.
Rémy Belmonte +2 more
doaj +1 more source
Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry [PDF]
ACM Symposium on Parallelism in Algorithms and Architectures, 2018 In this paper, we design parallel write-efficient geometric algorithms that perform asymptotically fewer writes than standard algorithms for the same problem.
G. Blelloch +3 more
semanticscholar +1 more source
Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 We initiate the study of a new problem on searching and fetching in a distributed environment concerning treasure-evacuation from a unit disk. A treasure and an exit are located at unknown positions on the perimeter of a disk and at known arc distance. A
Konstantinos Georgiou +2 more
doaj +1 more source
Improved Combinatorial Approximations for Weighted Correlation Clustering [PDF]
Discrete Mathematics & Theoretical Computer ScienceWe present combinatorial approximation algorithms for the weighted correlation clustering problem. In this problem, we have a set of vertices and two weight values for each pair of vertices, denoting their difference and similarity.
Mojtaba Ostovari, Alireza Zarei
doaj +1 more source
Longest Gapped Repeats and Palindromes [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 A gapped repeat (respectively, palindrome) occurring in a word $w$ is a factor $uvu$ (respectively, $u^Rvu$) of $w$. In such a repeat (palindrome) $u$ is called the arm of the repeat (respectively, palindrome), while $v$ is called the gap. We show how to
Marius Dumitran +2 more
doaj +1 more source
Structural Parameterizations of the Biclique-Free Vertex Deletion Problem [PDF]
Discrete Mathematics & Theoretical Computer ScienceIn this work, we study the Biclique-Free Vertex Deletion problem: Given a graph $G$ and integers $k$ and $i \le j$, find a set of at most $k$ vertices that intersects every (not necessarily induced) biclique $K_{i, j}$ in $G$.
Lito Goldmann +2 more
doaj +1 more source
An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 We present a polynomial time algorithm, which solves a nonstandard Variation of the well-known PARTITION-problem: Given positive integers $n, k$ and $t$ such that $t \geq n$ and $k \cdot t = {n+1 \choose 2}$, the algorithm partitions the elements of the ...
Alexander Büchel +2 more
doaj +1 more source
An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 Given a graph $G=(V,E)$ and a positive integer $t\geq2$, the task in the vertex cover $P_t$ ($VCP_t$) problem is to find a minimum subset of vertices $F\subseteq V$ such that every path of order $t$ in $G$ contains at least one vertex from $F$.
Zongwen Bai, Jianhua Tu, Yongtang Shi
doaj +1 more source
Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms [PDF]
Groups, Complexity, Cryptology, 2022 We study the problems of testing isomorphism of polynomials, algebras, and multilinear forms. Our first main results are average-case algorithms for these problems. For example, we develop an algorithm that takes two cubic forms $f, g\in \mathbb{F}_q[x_1,
Joshua A. Grochow +2 more
doaj +1 more source