Search results for " Computer Science"
showing 10 items of 3983 documents
On the loopless generation of binary tree sequences
1998
Weight sequences were introduced by Pallo in 1986 for coding binary trees and he presented a constant amortized time algorithm for their generation in lexicographic order. A year later, Roelants van Baronaigien and Ruskey developed a recursive constant amortized time algorithm for generating Gray code for binary trees in Pallo's representation. It is common practice to find a loopless generating algorithm for a combinatorial object when enunciating a Gray code for this object. In this paper we regard weight sequences as variations and apply a Williamson algorithm in order to obtain a loopless generating algorithm for the Roelants van Baronaigien and Ruskey's Gray code for weight sequences.
Potential approach in marginalizing Gibbs models
1999
Abstract Given an undirected graph G or hypergraph potential H model for a given set of variables V , we introduce two marginalization operators for obtaining the undirected graph G A or hypergraph H A associated with a given subset A ⊂ V such that the marginal distribution of A factorizes according to G A or H A , respectively. Finally, we illustrate the method by its application to some practical examples. With them we show that potential approach allow defining a finer factorization or performing a more precise conditional independence analysis than undirected graph models. Finally, we explain connections with related works.
Grundy coloring for power graphs
2003
International audience
Partially Square Graphs, Hamiltonicity and Circumference II
2000
Abstract Given a graph G, its partially square graph G∗ is a graph obtained by adding an edge uv for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition NG(x) ⊆ NG[u] ∪ NG[v], where NG[x]= NG(x) ∪ {x}. In case G is a claw-free graph, G∗ is equal to G2, We define σ ∗ t = min{ ∑ x∈ d ∗ G (x): S is an independent set in G ∗ and ∣S∣ = t} , where d ∗ G (x) = ∣{y ∈ V∣ xy ∈ E(G∗)}∣ . We give for hamiltonicity and circumference new sufficient conditions depending on and we improve some known results.
Forbidden words in symbolic dynamics
2000
AbstractWe introduce an equivalence relation≃between functions from N to N. By describing a symbolic dynamical system in terms of forbidden words, we prove that the≃-equivalence class of the function that counts the minimal forbidden words of a system is a topological invariant of the system. We show that the new invariant is independent from previous ones, but it is not characteristic. In the case of sofic systems, we prove that the≃-equivalence of the corresponding functions is a decidable question. As a more special application, we show, by using the new invariant, that two systems associated to Sturmian words having “different slope” are not conjugate.
Divisible designs from semifield planes
2002
AbstractWe give a general method to construct divisible designs from semifield planes and we use this technique to construct some divisible designs. In particular, we give the case of twisted field plane as an example.
Root-restricted Kleenean rotations
2010
We generalize the Kleene theorem to the case where nonassociative products are used. For this purpose, we apply rotations restricted to the root of binary trees.
Generation of Valid Labeled Binary Trees
2003
International audience; Generating binary trees is a well-known problem. In this paper, we add some constraints to leaves of these trees. Such trees are used in the morphing of polygons, where a polygon P is represented by a binary tree T and each angle of P is a weight on a leaf of T. In the following, we give two algorithms to generate all binary trees, without repetitions, having the same weight distribution to their leaves and representing all parallel polygons to P.
A bijection between words and multisets of necklaces
2012
Two of the present authors have given in 1993 a bijection Phi between words on a totally ordered alphabet and multisets of primitive necklaces. At the same time and independently, Burrows and Wheeler gave a data compression algorithm which turns out to be a particular case of the inverse of Phi. In the present article, we show that if one replaces in Phi the standard permutation of a word by the co-standard one (reading the word from right to left), then the inverse bijection is computed using the alternate lexicographic order (which is the order of real numbers given by continued fractions) on necklaces, instead of the lexicographic order as for Phi(-1). The image of the new bijection, ins…
Total and fractional total colourings of circulant graphs
2008
International audience; In this paper, the total chromatic number and the fractional total chromatic number of circulant graphs are studied. For cubic circulant graphs we give upper bounds on the fractional total chromatic number and for 4-regular circulant graphs we find the total chromatic number for some cases and we give the exact value of the fractional total chromatic number in most cases.