Results 11 to 20 of about 698 (72)
On Minimal Strings Containing the Elements of S_n by Decimation [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 The permutations by decimation problem is thought to be applicable to computer graphics, and raises interesting theoretical questions in combinatory theory.We present the results of some theoretical and practical investigation into this problem.We show ...
Robert Erra, Nik Lygeros, Nigel Stewart
doaj +1 more source
Pseudo-Permutations II: Geometry and Representation Theory [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 In this paper, we provide the second part of the study of the pseudo-permutations. We first derive a complete analysis of the pseudo-permutations, based on hyperplane arrangements, generalizing the usual way of translating the permutations. We then study
François Boulier +3 more
doaj +1 more source
The Chip Firing Game and Matroid Complexes [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 In this paper we construct from a cographic matroid M, a pure multicomplex whose degree sequence is the h―vector of the the matroid complex of M. This result provesa conjecture of Richard Stanley [Sta96] in the particular case of cographic matroids.
Criel Merino
doaj +1 more source
Gardens of Eden and Fixed Points in Sequential Dynamical Systems [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 A class of finite discrete dynamical systems, called Sequential Dynamical Systems (SDSs), was proposed in [BMR99,BR99] as an abstract model of computer simulations.
Christopher Barrett +6 more
doaj +1 more source
Mixing Times of Plane Random Rhombus Tilings [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 We address the question of single flip discrete dynamics in sets of two-dimensional random rhombus tilings with fixed polygonal boundaries. Single flips are local rearrangements of tiles which enable to sample the configuration sets of tilings via Markov
Nicolas Destainville
doaj +1 more source
Randomized Optimization: a Probabilistic Analysis [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 In 1999, Chan proposed an algorithm to solve a given optimization problem: express the solution as the minimum of the solutions of several subproblems and apply the classical randomized algorithm for finding the minimum of $r$ numbers.
Jean Cardinal +2 more
doaj +1 more source
On the Ehrenfeucht-Mycielski Balance Conjecture [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 In 1992, A. Ehrenfeucht and J. Mycielski defined a seemingly pseudorandom binary sequence which has since been termed the EM-sequence. The balance conjecture for the EM-sequence, still open, is the conjecture that the sequence of EM-sequence initial ...
John C. Kieffer, W. Szpankowski
doaj +1 more source
Computational Geometry Column 39 [PDF]
, 2000 The resolution of a decades-old open problem is described: polygonal chains cannot lock in the plane.Comment: 4 pages, 2 figures. To appear in SIGACT News and in Int. J. Comp.
O'Rourke, Joseph
core +3 more sources
Periodic Patterns in Orbits of Certain Linear Cellular Automata [PDF]
Discrete Mathematics & Theoretical Computer Science, 2001 We discuss certain linear cellular automata whose cells take values in a finite field. We investigate the periodic behavior of the verticals of an orbit of the cellular automaton and establish that there exists, depending on the characteristic of the ...
André Barbé, Fritz Haeseler
doaj +1 more source
Vertex-Unfoldings of Simplicial Polyhedra [PDF]
, 2001 We present two algorithms for unfolding the surface of any polyhedron, all of whose faces are triangles, to a nonoverlapping, connected planar layout. The surface is cut only along polyhedron edges. The layout is connected, but it may have a disconnected
Demaine, Erik D. +4 more
core +5 more sources