Search results for "combinatoric"
showing 10 items of 1776 documents
Special factors and the combinatorics of suffix and factor automata
2011
AbstractThe suffix automaton (resp. factor automaton) of a finite word w is the minimal deterministic automaton recognizing the set of suffixes (resp. factors) of w. We study the relationships between the structure of the suffix and factor automata and classical combinatorial parameters related to the special factors of w. We derive formulae for the number of states of these automata. We also characterize the languages LSA and LFA of words having respectively suffix automaton and factor automaton with the minimal possible number of states.
Grover’s Search with Faults on Some Marked Elements
2016
Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size N using $$O\sqrt{N}$$ queries. It provides a significant speed-up over any classical algorithm [2]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [1, 4]. We study the behavior of Grover's algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of marked elements in $$O\sqrt{N}$$ queries.
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 …
Stable maps from surfaces to the plane with prescribed branching data
2007
Abstract We consider the problem of constructing stable maps from surfaces to the plane with branch set a given set of curves immersed (except possibly with cusps) in the plane. Various constructions are used (1) piecing together regions immersed in the plane (2) modifying an existing stable map by a sequence of codimension one transitions (swallowtails etc) or by surgeries. In (1) the way the regions are pieced together is described by a bipartite graph (an edge C* corresponds to a branch curve C with the vertices of C* corresponding to the two regions containing C). We show that any bipartite graph may be realized by a stable map and we consider the question of realizing graphs by fold ma…
The Shuffle Product: New Research Directions
2015
In this paper we survey some recent researches concerning the shuffle operation that arise both in Formal Languages and in Combinatorics on Words.
EMERGENCE OF TRAVELLING WAVES IN SMOOTH NERVE FIBRES
2008
International audience; An approximate analytical solution characterizing initial condi- tions leading to action potential ¯ring in smooth nerve ¯bres is determined, using the bistable equation. In the ¯rst place, we present a non-trivial sta- tionary solution wave. Then, we extract the main features of this solution to obtain a frontier condition between the initiation of the travelling waves and a decay to the resting state. This frontier corresponds to a separatrix in the projected dynamics diagram depending on the width and the amplitude of the stationary wave.
Optimal signed-rank tests based on hyperplanes
2005
Abstract For analysing k -variate data sets, Randles (J. Amer. Statist. Assoc. 84 (1989) 1045) considered hyperplanes going through k - 1 data points and the origin. He then introduced an empirical angular distance between two k -variate data vectors based on the number of hyperplanes (the so-called interdirections ) that separate these two points, and proposed a multivariate sign test based on those interdirections. In this paper, we present an analogous concept (namely, lift-interdirections ) to measure the regular distances between data points. The empirical distance between two k -variate data vectors is again determined by the number of hyperplanes that separate these two points; in th…
An alternative representation of Altham's multiplicative-binomial distribution
1998
Abstract Cox (1972) introduced a log-linear representation for the joint distribution of n binary-dependent responses. Altham (1978) derived the distribution of the sum of such responses, under a multiplicative, rather than log-linear, representation and called it multiplicative-binomial. We propose here an alternative form of the multiplicative-binomial, which is derived from the original Cox's representation and is characterized by intuitively meaningful parameters, and compare its first two moments with those of the standard binomial distribution.
A Log-Rank Test for Equivalence of Two Survivor Functions
1993
We consider a hypothesis testing problem in which the alternative states that the vertical distance between the underlying survivor functions nowhere exceeds some prespecified bound delta0. Under the assumption of proportional hazards, this hypothesis is shown to be (logically) equivalent to the statement [beta[log(1 + epsilon), where beta denotes the regression coefficient associated with the treatment group indicator, and epsilon is a simple strictly increasing function of delta. The testing procedure proposed consists of carrying out in terms of beta (i.e., the standard Cox likelihood estimator of beta) the uniformly most powerful level alpha test for a suitable interval hypothesis about…