Search results for "Computation Theory & Mathematics"
showing 10 items of 332 documents
Radio k-Labelings for Cartesian Products of Graphs
2005
International audience; Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that |f(x)−f(y)| ≥ k+1−dG(x,y), for any two vertices x and y, where dG(x,y) is the distance between x and y in G. The radio k-chromatic number is the minimum of max{f(x)−f(y):x,y ∈ V(G)} over all radio k-labelings f of G. In this paper we present the radio k-labeling for the Cartesian pro…
A branch-and-cut algorithm for the soft-clustered vehicle-routing problem
2021
Abstract The soft-clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem (CVRP) in which customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. We introduce a novel symmetric formulation of the problem in which the clustering part is modeled with an asymmetric sub-model. We solve the new model with a branch-and-cut algorithm exploiting some known valid inequalities for the CVRP that can be adapted. In addition, we derive problem-specific cutting planes and new heuristic and exact separation procedures. For square grid instances in the Euclidean plane, we provide lower-bounding techniques …
The rank of random regular digraphs of constant degree
2018
Abstract Let d be a (large) integer. Given n ≥ 2 d , let A n be the adjacency matrix of a random directed d -regular graph on n vertices, with the uniform distribution. We show that the rank of A n is at least n − 1 with probability going to one as n grows to infinity. The proof combines the well known method of simple switchings and a recent result of the authors on delocalization of eigenvectors of A n .
Talking Blockchains: The Perspective of a Database Researcher
2021
There are few topics out there, that seem to create as much confusion and discussion as blockchains. This has a multitude of reasons: (1) A large number of drastically different concepts and systems are unified under the very broad term "blockchain". (2) The topic touches a variety of different fields, including databases, distributed processing, networks, cryptography, and even economics. (3) There exists a large number of different applications of the technology.The goal of this paper is to simplify and structure the discussion of blockchain technology. We first introduce a simple formalization of the basic components, that appear again and again in a variety of blockchain systems. Second…
Underlying Simple Graphs
2019
Summary In this article the notion of the underlying simple graph of a graph (as defined in [8]) is formalized in the Mizar system [5], along with some convenient variants. The property of a graph to be without decorators (as introduced in [7]) is formalized as well to serve as the base of graph enumerations in the future.
A study on graph representations for genetic programming
2020
Graph representations promise several desirable properties for Genetic Programming (GP); multiple-output programs, natural representations of code reuse and, in many cases, an innate mechanism for neutral drift. Each graph GP technique provides a program representation, genetic operators and overarching evolutionary algorithm. This makes it difficult to identify the individual causes of empirical differences, both between these methods and in comparison to traditional GP. In this work, we empirically study the behavior of Cartesian Genetic Programming (CGP), Linear Genetic Programming (LGP), Evolving Graphs by Graph Programming (EGGP) and traditional GP. By fixing some aspects of the config…
Classical and Quantum Computations with Restricted Memory
2018
Automata and branching programs are known models of computation with restricted memory. These models of computation were in focus of a large number of researchers during the last decades. Streaming algorithms are a modern model of computation with restricted memory. In this paper, we present recent results on the comparative computational power of quantum and classical models of branching programs and streaming algorithms.
On the role of non-effective code in linear genetic programming
2019
In linear variants of Genetic Programming (GP) like linear genetic programming (LGP), structural introns can emerge, which are nodes that are not connected to the final output and do not contribute to the output of a program. There are claims that such non-effective code is beneficial for search, as it can store relevant and important evolved information that can be reactivated in later search phases. Furthermore, introns can increase diversity, which leads to higher GP performance. This paper studies the role of non-effective code by comparing the performance of LGP variants that deal differently with non-effective code for standard symbolic regression problems. As we find no decrease in p…
Efficient evaluation for a subset of recursive queries
1991
Abstract We consider the efficient evaluation of recursive queries in logic databases where the queries are expressed using a Datalog program (function-free Horn-clause program) that contains only regularly or linearly recursive predicates. Using well-known results on graph traversal, we develop an efficient algorithm for evaluating relations defined by a binary-chain program. We also present a transformation by which the evaluation of a subset of queries involving nonbinary relations can be reduced to the evaluation of binary-chain queries. This transformation is guided by the choice of bound arguments in the query, and the bindings are propagated through the program so that in the evaluat…
Dictionary-symbolwise flexible parsing
2012
AbstractLinear-time optimal parsing algorithms are rare in the dictionary-based branch of the data compression theory. A recent result is the Flexible Parsing algorithm of Matias and Sahinalp (1999) that works when the dictionary is prefix closed and the encoding of dictionary pointers has a constant cost. We present the Dictionary-Symbolwise Flexible Parsing algorithm that is optimal for prefix-closed dictionaries and any symbolwise compressor under some natural hypothesis. In the case of LZ78-like algorithms with variable costs and any, linear as usual, symbolwise compressor we show how to implement our parsing algorithm in linear time. In the case of LZ77-like dictionaries and any symbol…