Theoretical Computer Science

Given a set R of robots, each one located at a different vertex of an infinite regular tessellation graph, we aim to explore the Arbitrary Pattern Formation (APF) problem. Given a multiset F of grid vertices such that | R | = | F |, ...

• We solve the Arbitrary Pattern Formation problem for asynchronous robots moving on triangular grids.

This work considers the Minimum Path-Collection Exact Cover (PCEC) and the Minimum k-Path Splitting Exact Cover (k-PSEC). Both problems receive a digraph G and a set P of paths in G, and their objective is to find a minimum cardinality ...

The line graphs of some well-known graphs, such as the generalized hypercube and the crossed cube, have been adopted for the logic graphs of data center networks (DCNs). Conditional bijective connection networks (conditional BC ...

To introduce our question and the parameterization, consider the classical Vertex Cover problem. In this problem, the input is a graph G on n vertices and a positive integer ℓ, and the goal is to find a vertex subset S of size at most ...

Existing graph-theoretic approaches to construct floor-plans for a given plane graph are mainly restricted to floor-plans with rectangular boundary. This paper introduces floor-plans with L-shaped boundary (boundary with only one ...

• Construction of floorplans for a given graph is limited to rectangular boundaries.

By using the PoW protocol, mining pools compete to successfully mine blocks to pursue rewards. Generally, the reward from a mined block includes the fixed block subsidies and the time-varying transaction fees. The latter are offered by ...

• A framework is built for the general evolutionary game.
• Based on the analysis ...

The squared metric k-facility location problem is a frequently encountered generalization of the k-means problem, where a specific cost should be paid for opening each facility. The current best approximation ratio for this problem is ...

• We give a ( 36.342 + ϵ )-approximation algorithm for the squared metric k-facility location problem.

This paper proposes the first implementation of a self-stabilizing regular register emulated by n servers that is tolerant to both Mobile Byzantine Agents and transient failures in a round-free synchronous model. Differently from ...

We consider a discrete system of n simple indistinguishable devices, called agents, forming a connected shape S I on a two-dimensional square grid. Agents are equipped with a linear-strength mechanism, called a line move, by which an ...

• We study a linear-strength model for programmable matter and mobile robotic systems

Randomized dimensionality reduction has been recognized as one of the cornerstones in handling high-dimensional data, originating in various foundational works such as the celebrated Johnson-Lindenstrauss Lemma. More specifically, ...

The suffix array, perhaps the most important data structure in modern string processing, is often augmented with the longest common prefix (LCP) array which stores the lengths of the longest common prefixes for lexicographically ...

We define the mod P-synchronization problem as a weakening of the firing squad problem, where all nodes fire not at the same round, but at rounds that are all equal modulo P. We introduce an algorithm that achieves mod P-...

• We define a weakening of the firing squad problem, in which all nodes fire at rounds that are all equal modulo P.

We consider a known variant of bin packing called cardinality constrained bin packing, also called bin packing with cardinality constraints (BPCC). In this problem, there is a parameter k ≥ 2, and items of rational sizes in [ 0 , 1 ] ...

Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets ...

We study the problem of deciding reconfigurability of target sets of a graph. Given a graph G with vertex thresholds τ, consider a dynamic process in which vertex v becomes activated once at least τ ( v ) of its neighbors are ...

Numerous fundamental database and reasoning problems are known to be NP-hard in general but tractable on instances where the underlying hypergraph structure is β-acyclic. Despite the importance of many of these problems, there has been ...

With the rapid and continuous development of network technology, a multiprocessor system, consisting of multiple processors and communication links, plays an significant role in big data era. The topology of a multiprocessor system is ...