Results 1 to 10 of about 347,865 (289)
Exactly Hittable Interval Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 Given a set system $\mathcal{X} = \{\mathcal{U},\mathcal{S}\}$, where $\mathcal{U}$ is a set of elements and $\mathcal{S}$ is a set of subsets of $\mathcal{U}$, an exact hitting set $\mathcal{U}'$ is a subset of $\mathcal{U}$ such that each subset in ...
S. M. Dhannya +2 more
doaj +1 more source
Testing Distributions of Huge Objects [PDF]
TheoretiCS, 2023 We initiate a study of a new model of property testing that is a hybrid of testing properties of distributions and testing properties of strings. Specifically, the new model refers to testing properties of distributions, but these are distributions over ...
Oded Goldreich, Dana Ron
doaj +1 more source
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
Evacuating Robots from a Disk Using Face-to-Face Communication [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 Assume that two robots are located at the centre of a unit disk. Their goal is to evacuate from the disk through an exit at an unknown location on the boundary of the disk.
Jurek Czyzowicz +5 more
doaj +1 more source
BDD-Based Algorithm for SCC Decomposition of Edge-Coloured Graphs [PDF]
Logical Methods in Computer Science, 2022 Edge-coloured directed graphs provide an essential structure for modelling and analysis of complex systems arising in many scientific disciplines (e.g. feature-oriented systems, gene regulatory networks, etc.).
Nikola Beneš +3 more
doaj +1 more source
Parameterized Power Vertex Cover [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 We study a recently introduced generalization of the Vertex Cover (VC) problem, called Power Vertex Cover (PVC). In this problem, each edge of the input graph is supplied with a positive integer demand.
Eric Angel +3 more
doaj +1 more source
Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring [PDF]
TheoretiCS, 2023 Every graph with maximum degree $\Delta$ can be colored with $(\Delta+1)$ colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model.
Sepehr Assadi +2 more
doaj +1 more source
On-line algorithms for multiplication and division in real and complex numeration systems [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 A positional numeration system is given by a base and by a set of digits. The base is a real or complex number $\beta$ such that $|\beta|>1$, and the digit set $A$ is a finite set of digits including $0$. Thus a number can be seen as a finite or infinite
Christiane Frougny +3 more
doaj +1 more source
Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 In this article we focus on the parameterized complexity of the Multidimensional Binary Vector Assignment problem (called \BVA). An input of this problem is defined by $m$ disjoint sets $V^1, V^2, \dots, V^m$, each composed of $n$ binary vectors of size $
Marin Bougeret +3 more
doaj +1 more source
Fast Diameter Computation within Split Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 When can we compute the diameter of a graph in quasi linear time? We address this question for the class of {\em split graphs}, that we observe to be the hardest instances for deciding whether the diameter is at most two.
Guillaume Ducoffe +2 more
doaj +1 more source