@Article{DMTCS-010101,
author = {Csaba Schneider},
title = {Computing nilpotent quotients in finitely presented {L}ie rings},
keywords = {Lie rings, nilpotent Lie rings, finitely presented Lie rings, nilpotent presentation },
abstract = {A nilpotent quotient algorithm for finitely presented Lie rings over {${\textbf{Z}}$} (and {${\textbf{Q}}$}) is
described. The paper studies the graded and non-graded cases
separately. The algorithm computes the so-called nilpotent
presentation for a finitely presented, nilpotent Lie ring. A nilpotent
presentation consists of generators for the abelian group and the
products expressed as linear combinations for pairs formed by
generators. Using that presentation the word problem is decidable in
{${L}$}. Provided that the Lie ring
{${L}$} is graded, it is possible to determine the
canonical presentation for a lower central factor of
{${L}$}. Complexity is studied and it is shown that
optimising the presentation is NP-hard. Computational details are
provided with examples, timing and some structure theorems obtained
from computations. Implementation in C and GAP interface are
available.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {1-16},
url = {http://www.dmtcs.org/volumes/abstracts/dm010101.abs.html}
}
@Article{DMTCS-010102,
author = {V. Giakoumakis and F. Roussel and H. Thuillier},
title = {On {${P_{4}}$}-tidy graphs},
keywords = {graph modular decomposition, perfection {${P_{4}}$}-structure },
abstract = {We study the {${P_{4}}$}-tidy graphs, a new class defined by Rusu [30] in order to illustrate the notion of {${P_{4}}$}-domination in
perfect graphs. This class strictly contains the {${P_{4}}$}-extendible graphs and
the {${P_{4}}$}-lite graphs defined by Jamison \& Olariu in [19] and [23] and we
show that the {${P_{4}}$}-tidy graphs and {${P_{4}}$}-lite graphs are closely related. Note
that the class of {${P_{4}}$}-lite graphs is a class of brittle graphs strictly containing
the {${P_{4}}$}-sparse graphs defined by Hoang in [14]. McConnel \& Spinrad [2]
and independently Cournier \& Habib [5] have shown that the modular
decomposition tree of any graph is computable in linear time. For recognizing
in linear time {${P_{4}}$}-tidy graphs, we apply a method introduced by Giakoumakis
in [9] and Giakoumakis \& Fouquet in [6] using modular decomposition of
graphs and we propose linear algorithms for optimization problems on such
graphs, as clique number, stability number, chromatic number and scattering
number. We show that the Hamiltonian Path Problem is linear for this class
of graphs. Our study unifies and generalizes previous results of Jamison
\& Olariu ([18], [21], [22]), Hochstattler \& Schindler[16], Jung [25]
and Hochstattler \& Tinhofer [15].},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {17-41},
url = {http://www.dmtcs.org/volumes/abstracts/dm010102.abs.html}
}
@Article{DMTCS-010103,
author = {Augustin Ido and Guy Melan\c{c}on},
title = {{L}yndon factorization of the {T}hue-{M}orse word and its relatives},
keywords = {Lyndon factorization, Thue-Morse word, morphisms },
abstract = {We compute the Lyndon factorization of the Thue-Morse word. We also compute the Lyndon factorization of two related
sequences involving morphisms that give rise to new presentations of these
sequences.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {43-52},
url = {http://www.dmtcs.org/volumes/abstracts/dm010103.abs.html}
}
@Article{DMTCS-010104,
author = {Jean-Christophe Novelli and Igor Pak and Alexander V. Stoyanovskii},
title = {A direct bijective proof of the hook-length formula},
keywords = {Hook-length formula, bijective proof, inverse algorithms },
abstract = {This paper presents a new proof of the hook-length formula, which computes the number of standard Young tableaux
of a given shape. After recalling the basic definitions, we present two inverse
algorithms giving the desired bijection. The next part of the paper presents
the proof of the bijectivity of our construction. The paper concludes with
some examples.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {53-67},
url = {http://www.dmtcs.org/volumes/abstracts/dm010104.abs.html}
}
@Article{DMTCS-010105,
author = {S{\'e}bastien Limet and Pierre R{\'e}ty},
title = {{E}-unification by means of tree tuple synchronized grammars},
keywords = {{E}-unification, narrowing, tree languages, decidability},
abstract = {The goal of this paper is both to give an {E}-unification procedure that always terminates, and to decide unifiability.
For this, we assume that the equational theory is specified by a confluent
and constructor-based rewrite system, and that four additional restrictions
are satisfied. We give a procedure that represents the (possibly infinite)
set of solutions thanks to a tree tuple synchronized grammar, and that can
decide upon unifiability thanks to an emptiness test. Moreover, we show that
if only three of the four additional restrictions are satisfied then unifiability
is undecidable.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {69-98},
url = {http://www.dmtcs.org/volumes/abstracts/dm010105.abs.html}
}
@Article{DMTCS-010106,
author = {G{\'e}rard Jacob and Pierre-Vincent Koseleff},
title = {{Special issue: 'Lie Computations'}},
keywords = {Lie computations, special issue},
abstract = {This special issue is an outgrowth of the MEDICIS thematic workshop on Lie Computations that was held at the Centre
International de Rencontres Math{\'e}matiques in Marseilles in November
1994. It was jointly sponsored by the Groupe de Recherche MEDICIS, the CIRM
(Soci{\'e}t{\'e} Math{\'e}matique de France), and the European project
INTAS 93-30.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {99-100},
url = {http://www.dmtcs.org/volumes/abstracts/dm010106.abs.html}
}
@Article{DMTCS-010107,
author = {Philippe Andary},
title = {Finely homogeneous computations in free {L}ie algebras},
keywords = {Lie algebras, finely homogeneous computations},
abstract = {We first give a fast algorithm to compute the maximal Lyndon word (with respect to lexicographic order) of
{${\textit{Ly}_{\alpha }(A)}$} for every given multidegree
alpha in {${\textbf{N}^{k}}$}. We then give an algorithm
to compute all the words living in
{${\textit{Ly}_{\alpha }(A)}$} for any given
{${\alpha }$} in {${\textbf{N}^{k}}$}. The best
known method for generating Lyndon words is that of Duval [1], which
gives a way to go from every Lyndon word of length {${n}$} to
its successor (with respect to lexicographic order by length), in
space and worst case time complexity {${O(n)}$}. Finally, we
give a simple algorithm which uses Duval's method (the one above) to
compute the next standard bracketing of a Lyndon word for
lexicographic order by length. We can find an interesting application
of this algorithm in control theory, where one wants to compute within
the command Lie algebra of a dynamical system (letters are actually
vector fields).},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {101-114},
url = {http://www.dmtcs.org/volumes/abstracts/dm010107.abs.html}
}
@Article{DMTCS-010108,
author = {H. Caprasse},
title = {{B}{R}{S}{T} Charge and {P}oisson Algebras},
keywords = {guage theory, BRST symmetry},
abstract = {An elementary introduction to the classical version of gauge theories is made. The shortcomings of the usual gauge fixing
process are pointed out. They justify the need to replace it by a global
symmetry: the BRST symmetry and its associated BRST charge. The main mathematical
steps required to construct it are described. The algebra of constraints
is, in general, a nonlinear Poisson algebra. In the nonlinear case the
computation of the BRST charge by hand is hard. Itis explained how this
computation can be made algorithmic. The main features of a recently created
BRST computer algebra program are described. It can handle quadratic algebras
very easily. Its capability to compute the BRST charge as a formal power
series in the generic case of a cubic algebra is illustrated.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {115-127},
url = {http://www.dmtcs.org/volumes/abstracts/dm010108.abs.html}
}
@Article{DMTCS-010109,
author = {Cohen, A. M. and de Graaf, W. A. and R{\'o}nyai, L.},
title = {Computations in finite-dimensional {L}ie algebras},
keywords = {Lie algebra algorithms, ELIAS},
abstract = {This paper describes progress made in context with the construction of a general library of Lie algebra algorithms, called
ELIAS (Eindhoven Lie Algebra System), within the computer algebra
package GAP. A first sketch of the package can be found in Cohen and
de Graaf[1]. Since then, in a collaborative effort with
G.\ Ivanyos, the authors have continued to develop algorithms
which were implemented in ELIAS by the second author. These
activities are part of a bigger project, called ACELA and financed by
STW, the Dutch Technology Foundation, which aims at an interactive
book on Lie algebras (cf. Cohen and Meertens [2]). This paper gives a
global description of the main ways in which to present Lie algebras
on a computer. We focus on the transition from a Lie algebra
abstractly given by an array of structure constants to a Lie algebra
presented as a subalgebra of the Lie algebra of {${n{\times}n}$}
matrices. We describe an algorithm typical of the structure analysis
of a finite-dimensional Lie algebra: finding a Levi subalgebra of a
Lie algebra.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {129-138},
url = {http://www.dmtcs.org/volumes/abstracts/dm010109.abs.html}
}
@Article{DMTCS-010110,
author = {S. Cojocaru and V. Ufnarovski},
title = {{BERGMAN} under {MS-DOS} and {Anick's} resolution},
keywords = {Gr{\"o}bner basis, Hilbert series, resolution},
abstract = {Noncommutative algebras, defined by the generators and relations, are considered. The definition and main results
connected with the Gr{\"o}bner basis, Hilbert series and Anick's resolution
are formulated. Most attention is paid to universal enveloping algebras.
Four main examples illustrate the main concepts and ideas. Algorithmic problems
arising in the calculation of the Hilbert series are investigated. The existence
of finite state automata, defining thebehaviour of the Hilbert series, is
discussed. The extensions of the BERGMAN package for IBM PC compatible computers
are described. A table is provided permitting a comparison of the effectiveness
of the calculations in BERGMAN with the other systems.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {139-147},
url = {http://www.dmtcs.org/volumes/abstracts/dm010110.abs.html}
}
@Article{DMTCS-010111,
author = {Alex J. Dragt},
title = {A {L}ie connection between {H}amiltonian and {L}agrangian optics},
keywords = {Lie algebra, Hamiltonian and Lagrangian optics},
abstract = {It is shown that there is a non-Hamiltonian vector field that provides a Lie algebraic connection between Hamiltonian
and Lagrangian optics. With the aid of this connection, geometrical optics
can be formulated in such a way that all aberrations are attributed to ray
transformations occurring only at lens surfaces. That is, in this formulation
there are no aberrations arising from simple transit in a uniform medium.
The price to be paid for this formulation is that the Lie algebra of Hamiltonian
vector fields must be enlarged to include certain non-Hamiltonian vector
fields. It is shown that three such vector fields are required at the level
of third-order aberrations, and sufficient machinery is developed to generalize
these results to higher order.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {149-157},
url = {http://www.dmtcs.org/volumes/abstracts/dm010111.abs.html}
}
@Article{DMTCS-010112,
author = {G{\'e}rard Duchamp and Alexander Klyachko and Daniel Krob and Jean-Yves Thibon},
title = {Noncommutative symmetric functions {III}: {D}eformations of {C}auchy and convolution algebras},
keywords = {Symmetric functions, Descent algebras, Free Lie algebras, Quantum shuffle},
abstract = {This paper discusses various deformations of free associative algebras and of their convolution algebras. Our main
examples are deformations of noncommutative symmetric functions related to
families of idempotents in descent algebras, and a simple {${q}$}-analogue of the
shuffle product, which has unexpected connections with quantum groups, hyperplane
arrangements, and certain questions in mathematical physics (the quon algebra,
generalized Brownian motion).},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {159-216},
url = {http://www.dmtcs.org/volumes/abstracts/dm010112.abs.html}
}
@Article{DMTCS-010113,
author = {Vladimir P. Gerdt and Vladimir V. Kornyak},
title = {An algorithm for analysis of the structure of finitely presented {L}ie algebras},
keywords = {Lie algebras, structure analysis},
abstract = {We consider the following problem: what is the most general Lie algebra satisfying a given set of Lie polynomial
equations? The presentation of Lie algebras by a finite set of generators
and defining relations is one of the most general mathematical and algorithmic
schemes of their analysis. That problem is of great practical importance,
covering applications ranging from mathematical physics to combinatorial
algebra. Some particular applications are constructionof prolongation algebras
in the Wahlquist-Estabrook method for integrability analysis of nonlinear
partial differential equations and investigation of Lie algebras arising
in different physical models. The finite presentations also indicate a way
to q-quantize Lie algebras. To solve this problem, one should perform a large
volume of algebraic transformations which is sharply increased with growth
of the number of generators and relations. For this reason, in practice one
needs to use a computer algebra tool. We describe here an algorithm for
constructing the basis of a finitely presented Lie algebra and its commutator
table, and its implementation in the C language. Some computer results
illustrating our algorithmand its actual implementation are also
presented.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {217-228},
url = {http://www.dmtcs.org/volumes/abstracts/dm010113.abs.html}
}
@Article{DMTCS-010114,
author = {Maurice Ginocchio},
title = {On the bialgebra of functional graphs and differential algebras},
keywords = {bialgebraic structure, functional graphs, noncommutative polynomials},
abstract = {We develop the bialgebraic structure based on the set of functional graphs, which generalize the case of the forests of rooted
trees. We use noncommutative polynomials as generating monomials of
the functional graphs, and we introduce circular and arborescent
brackets in accordance with the decomposition in connected components
of the graph of a mapping of {${\{1, 2, {\ldots}, n\}}$} in
itself as in the frame of the discrete dynamical systems. We give
applications fordifferential algebras and algebras of differential
operators.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {229-237},
url = {http://www.dmtcs.org/volumes/abstracts/dm010114.abs.html}
}
@Article{DMTCS-010115,
author = {Yuri L. Sachkov},
title = {Controllability of affine right-invariant systems on solvable {L}ie groups},
keywords = {controllability, right-invariant system, Lie group},
abstract = {The aim of this paper is to present some recent results on controllability of right-invariant systems on Lie groups.
From the Lie-theoretical point of view, we study conditions under which
subsemigroups generated by half-planes in the Lie algebra of a Lie group
coincide with the whole Lie group.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {239-246},
url = {http://www.dmtcs.org/volumes/abstracts/dm010115.abs.html}
}
@Article{DMTCS-010116,
author = {Alois Panholzer and Helmut Prodinger},
title = {Descendants and ascendants in binary trees},
keywords = {binary tree, tree traversal, generating function, Zeilberger's algorithm },
abstract = {There are three classical algorithms to visit all the nodes of a binary tree - preorder, inorder and postorder
traversal. From this one gets a natural labelling of the n internal nodes
of a binary tree by the numbers {${1, 2, ..., n}$}, indicating the sequence in
which the nodes are visited. For given {${n}$} (size of the tree) and {${j}$} (a number
between {${1}$} and {${n}$}), we consider the statistics number of ascendants of node
{${j}$} and number of descendants of node {${j}$}. By appropriate trivariate generating
functions, we are able to find explicit formulae for the expectation and
the variance in all instances. The heavy computations that are necessary
are facilitated by MAPLE and Zeilberger's algorithm. A similar problem
comes fromlabelling the leaves from left to right by {${1, 2, ..., n}$} and considering
the statistic number of ascendants (=height) of leaf {${j}$}. For this, Kirschenhofer
[1] has computed the average. With our approach, we are also able to get
the variance. In the last section, a table with asymptotic equivalents is
provided for the reader's convenience. },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1997,
volume = {1},
number = {1},
pages = {247-266},
url = {http://www.dmtcs.org/volumes/abstracts/dm010116.abs.html}
}
@Article{DMTCS-020101,
author = {Christopher Lynch and Polina Strogova},
title = {{SOUR} graphs for efficient completion},
keywords = {SOUR graphs, completion algorithms},
abstract = {We introduce a data structure called \emph{SOUR} graphs and present an efficient Knuth-Bendix completion procedure based
on it. \emph{SOUR} graphs allow for a maximal structure sharing of terms in rewriting
systems. The term representation is a dag representation, except that edges
are labelled with equational constraints and variable renamings. The rewrite
rules correspond to rewrite edges, the unification problems to unification
edges. The Critical Pair and Simplification inferences are recognized as
patterns in the graph and are performed as local graph transformations. Our
algorithm avoids duplicating term structure while performing inferences,
which causes exponential behavior in the standard procedure. This approach
gives a basis to design other completion algorithms, such as goal-oriented
completion, concurrent completion and group completion
procedures.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1998,
volume = {2},
number = {1},
pages = {1-25},
url = {http://www.dmtcs.org/volumes/abstracts/dm020101.abs.html}
}
@Article{DMTCS-020102,
author = {Philippe Duchon},
title = {Right-cancellability of a family of operations on binary trees},
keywords = {binary trees},
abstract = {We prove some new results on a family of operations on binary trees, some of which are similar to addition,
multiplication and exponentiation for natural numbers. The main result is
that each operation in the family is right-cancellable.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1998,
volume = {2},
number = {1},
pages = {27-33},
url = {http://www.dmtcs.org/volumes/abstracts/dm020102.abs.html}
}
@Article{DMTCS-020103,
author = {Giovanni Manzini},
title = {Lower bounds for sparse matrix vector multiplication on hypercubic networks},
keywords = {Sparse matrices, pseudo expanders, hypercubic networks, bisection width lower bounds},
abstract = {In this paper we consider the problem of computing on a local memory machine the product {${y = Ax}$},where
{${A}$} is a random {${n{\times}n}$} sparse matrix with
{${\Theta (n)}$} nonzero elements. To study the average case
communication cost of this problem, we introduce four different
probability measures on the set of sparse matrices. We prove that on
most local memory machines with {${p}$} processors, this
computation requires {${\Omega ((n/p) \log p)}$} time on the
average. We prove that the same lower bound also holds, in the worst
case, for matrices with only {${2n}$} or {${3n}$}
nonzero elements.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1998,
volume = {2},
number = {1},
pages = {35-47},
url = {http://www.dmtcs.org/volumes/abstracts/dm020103.abs.html}
}
@Article{DMTCS-020104,
author = {I. Dutour and J. M. Fedou},
title = {Object grammars and random generation},
keywords = {Uniform random generation, object grammars, q-equations },
abstract = {This paper presents a new systematic approach for the uniform random generation of combinatorial objects. The
method is based on the notion of object grammars which give recursive
descriptions of objects and generalize context-freegrammars. The application
of particular valuations to these grammars leads to enumeration and random
generation of objects according to non algebraic parameters.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1998,
volume = {2},
number = {1},
pages = {49-63},
url = {http://www.dmtcs.org/volumes/abstracts/dm020104.abs.html}
}
@Article{DMTCS-030101,
author = {Ulrik Brandes and Dagmar Handke},
title = {\textit{NP}-Completeness Results for Minimum Planar Spanners},
keywords = {graph spanners, NP-completeness, planar graphs},
abstract = {For any fixed parameter {${t}$} greater or equal to {${1}$}, a \emph{ {${t}$}-spanner} of a graph {${G}$} is a
spanning subgraph in which the distance between every
pair of vertices is at most {${t}$} times their
distance in {${G}$}. A \emph{ minimum}
{${t}$}-spanner is a {${t}$}-spanner with minimum
total edge weight or, in unweighted graphs, minimum
number of edges. In this paper, we prove the
{${NP}$}-hardness of finding minimum
{${t}$}-spanners for planar weighted graphs and
digraphs if {${t}$} greater or equal to {${3}$},
and for planar unweighted graphs and digraphs if
{${t}$} greater or equal to {${5}$}. We thus extend
results on that problem to the interesting case where
the instances are known to be planar. We also
introduce the related problem of finding minimum
\emph{planar} {${t}$}-spanners and establish its
{${NP}$}-hardness for similar fixed values of
{${t}$}.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1998,
volume = {3},
number = {1},
pages = {1-10},
url = {http://www.dmtcs.org/volumes/abstracts/dm030101.abs.html}
}
@Article{DMTCS-030102,
author = {Christian Krattenthaler},
title = {An Involution Principle-Free Bijective Proof of {S}tanley's Hook-Content Formula },
keywords = {Stanley's Hook-Content Formula},
abstract = {A bijective proof for Stanley's hook-content formula for the generating function for column-strict reverse plane partitions of a
given shape is given that does not involve the involution principle of
Garsia and Milne. It is based on the Hillman-Grassl algorithm and
Sch{\"u}tzenberger's \emph{jeu\ de\ taquin}.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1998,
volume = {3},
number = {1},
pages = {11-32},
url = {http://www.dmtcs.org/volumes/abstracts/dm030102.abs.html}
}
@Article{DMTCS-030201,
author = {Elisha Falbel and Pierre-Vincent Koseleff},
title = {The Number of Sides of a Parallelogram},
keywords = {Lie algebras, free group, Magnus group, lower central series, Lyndon basis},
abstract = {We define parallelograms of base {${a}$} and {${b}$} in a group. They appear as minimal relators in a presentation of a subgroup with
generators {${a}$} and {${b}$}.
In a Lie group they are realized as closed polygonal lines, with sides
being orbits of left-invariant vector fields. We estimate the number of
sides of parallelograms in a free nilpotent group and point out a
relation to the rank of rational series. },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {2},
pages = {33-42},
url = {http://www.dmtcs.org/volumes/abstracts/dm030201.abs.html}
}
@Article{DMTCS-030202,
author = {Charles Knessl and Wojciech Szpankowski},
title = {Quicksort algorithm again revisited},
keywords = {Algorithms, Analysis of algorithms, Asymptotic analysis, Binary search tree, Quicksort, Sorting},
abstract = {We consider the standard Quicksort algorithm that sorts n distinct keys with all possible {${n!}$} orderings of keys
being equally likely. Equivalently, we analyze the total path length
{${L(n)}$} in a randomly built \emph{binary search
tree}. Obtaining the limiting distribution of {${L(n)}$} is
still an outstanding open problem. In this paper, we establish an
integral equation for the probability density of the number of
comparisons {${L(n)}$}. Then, we investigate the large
deviations of L(n). We shall show that the left tail of the limiting
distribution is much ``thinner'' (i.e., double exponential) than the
right tail (which is only exponential). Our results contain some
constants that must be determined numerically. We use formal
asymptotic methods of applied mathematics such as the WKB method and
matched asymptotics.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {2},
pages = {43-64},
url = {http://www.dmtcs.org/volumes/abstracts/dm030202.abs.html}
}
@Article{DMTCS-030203,
author = {Manfred G{\"o}bel},
title = {The Optimal Lower Bound for Generators of Invariant Rings without Finite {SAGBI} Bases with Respect to Any Admissible Order},
keywords = {SAGBI basis, Invariant ring, Analysis of algorithms},
abstract = {We prove the existence of an invariant ring {${\textbf{C}[X_{1},...,X_{n}]^{T}}$}
generated by elements with a total degree of at most {${2}$},
which has no finite SAGBI basis with respect to any admissible order.
Therefore, {${2}$} is the optimal lower bound for the total degree
of generators of invariant rings with such a property.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {2},
pages = {65-70},
url = {http://www.dmtcs.org/volumes/abstracts/dm030203.abs.html}
}
@Article{DMTCS-030301,
author = {Peter B{\"u}rgisser},
title = {On the Structure of {V}aliant's Complexity Classes},
keywords = {Structural complexity, Algebraic theories of NP-completeness diagonalization, Poset of degrees.},
abstract = {In Valiant developed an algebraic analogue of the theory of NP-completeness for computations of polynomials over a field. We
further develop this theory in the spirit of structural complexity and
obtain analogues of well-known results by Baker, Gill, and Solovay,
Ladner, and Sch{\"o}ning.\par
We show that if Valiant's hypothesis is
true, then there is a {${p}$}-definable family, which is
neither {${p}$}-computable nor \textit{VNP}-complete. More
generally, we define the posets of {${p}$}-degrees and
{${c}$}-degrees of {${p}$}-definable families and prove
that any countable poset can be embedded in either of them, provided
Valiant's hypothesis is true. Moreover, we establish the existence of
minimal pairs for \textit{VP} in \textit{VNP}.\par
Over finite fields, we
give a \emph{specific} example of a family of polynomials which is
neither \textit{VNP}-complete nor {${p}$}-computable, provided
the polynomial hierarchy does not collapse.\par
We define relativized
complexity classes {${VP^{h}}$} and
{${VNP^{h}}$} and construct complete families in these
classes. Moreover, we prove that there is a {${p}$}-family
{${h}$} satisfying {${VP^{h} =
VNP^{h}}$}.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {3},
pages = {73-94},
url = {http://www.dmtcs.org/volumes/abstracts/dm030301.abs.html}
}
@Article{DMTCS-030302,
author = {Kim S. Larsen},
title = {Partially persistent search trees with transcript operations},
keywords = {Data structures, Search trees, Persistence, Complexity.},
abstract = {When dictionaries are persistent, it is natural to introduce a transcript operation which reports the status changes for a given
key over time. We discuss when and how a time and space efficient
implementation of this operation can be provided.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {3},
pages = {95-107},
url = {http://www.dmtcs.org/volumes/abstracts/dm030302.abs.html}
}
@Article{DMTCS-030303,
author = {Thomas Schwentick and Klaus Barthelmann},
title = {Local Normal Forms for First-Order Logic with Applications to Games and Automata},
keywords = {First-order logic, existential monadic second-order logic, games, automata, locality},
abstract = {Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form
{${\exists x_{1},...,x_{l}, \forall y,
\phi }$} where {${\phi }$} is {${r}$}-local around
{${y}$}, i.e. quantification in {${\phi }$} is restricted
to elements of the universe of distance at most {${r}$} from
{${y}$}. \par
From this and related normal forms, variants
of the Ehrenfeucht game for first-order and existential monadic
second-order logic are developed that restrict the possible strategies
for the spoiler, one of the two players. This makes proofs of the
existence of a winning strategy for the duplicator, the other player,
easier and can thus simplify inexpressibility proofs. \par
As
another application, automata models are defined that have, on
arbitrary classes of relational structures, exactly the expressive
power of first-order logic and existential monadic second-order logic,
respectively.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {3},
pages = {109-124},
url = {http://www.dmtcs.org/volumes/abstracts/dm030303.abs.html}
}
@Article{DMTCS-030304,
author = {Anna Frid},
title = {Applying a uniform marked morphism to a word},
keywords = {D0L words, HD0L words, subword complexity, functions of a word},
abstract = {We describe the relationship between different parameters of the initial word and its image obtained by application of a uniform
marked morphism. The functions described include the subword
complexity, frequency of factors, and the recurrence function. The
relations obtained for the image of a word can be used also for the
image of a factorial language. Using induction, we give a full
description of the involved functions of the fixed point of the
morphism considered.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {3},
pages = {125-140},
url = {http://www.dmtcs.org/volumes/abstracts/dm030304.abs.html}
}
@Article{DMTCS-030401,
author = {Hans L. Bodlaender},
title = {A note on domino treewidth},
keywords = {Treewidth, Domino treewidth, Graph algorithms, Tree decompositions},
abstract = {In [DO95], Ding and Oporowski proved that for every {${k}$}, and {${d}$}, there exists a constant
{${c_{k,d}}$}, such that every graph with treewidth at
most {${k}$} and maximum degree at most {${d}$} has
domino treewidth at most {${c_{k,d}}$}. This note gives
a new simple proof of this fact, with a better bound for
{${c_{k,d}}$}, namely {${(9k+7)d(d+1) -1}$}. It
is also shown that a lower bound of {${\Omega (kd)}$} holds:
there are graphs with domino treewidth at least {${1/12 {\times}
kd-1}$}, treewidth at most {${k}$}, and maximum degree at
most {${d}$}, for many values {${k}$} and
{${d}$}. The domino treewidth of a tree is at most its maximum
degree.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {4},
pages = {141-150},
url = {http://www.dmtcs.org/volumes/abstracts/dm030401.abs.html}
}
@Article{DMTCS-030402,
author = {Aaron Robertson},
title = {Permutations Containing and Avoiding \textit{123} and \textit{132} Patterns},
keywords = {Patterns, Words},
abstract = {We prove that the number of permutations which avoid {${132}$}-patterns and have exactly one
{${123}$}-pattern, equals {${(n-2)2^{n-3}}$}, for
{${n\ge 3}$}. We then give a bijection onto the set of
permutations which avoid {${123}$}-patterns and have exactly
one {${132}$}-pattern. Finally, we show that the number of
permutations which contain exactly one {${123}$}-pattern and
exactly one {${132}$}-pattern is
{${(n-3)(n-4)2^{n-5}}$}, for {${n\ge 5}$}.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {4},
pages = {151-154},
url = {http://www.dmtcs.org/volumes/abstracts/dm030402.abs.html}
}
@Article{DMTCS-030403,
author = {Keqin Li},
title = {Analysis of an Approximation Algorithm for Scheduling Independent Parallel Tasks},
keywords = {Approximation algorithm, Average-case performance ratio, Parallel task scheduling, Probabilistic analysis,
Worst-case performance ratio},
abstract = {In this paper, we consider the problem of scheduling independent parallel tasks in parallel systems with identical
processors. The problem is NP-hard, since it includes the bin packing
problem as a special case when all tasks have unit execution time. We
propose and analyze a simple approximation algorithm called
{${H_{m}}$}, where {${m}$} is a positive
integer. Algorithm {${H_{m}}$} has a moderate
asymptotic worst-case performance ratio in the range
{${[4/3 ... 31/18]}$} for all {${m\ge 6}$}; but the
algorithm has a small asymptotic worst-case performance ratio in the
range {${[1+1/(r+1)..1+1/r]}$}, when task sizes do not exceed
{${1/r}$} of the total available processors, where
{${r>1}$} is an integer. Furthermore, we show that if the
task sizes are independent, identically distributed (i.i.d.) uniform
random variables, and task execution times are i.i.d. random variables
with finite mean and variance, then the average-case performance ratio
of algorithm {${H_{m}}$} is no larger than
1.2898680..., and for an exponential distribution of task sizes, it
does not exceed 1.2898305.... As demonstrated by our analytical as
well as numerical results, the average-case performance ratio improves
significantly when tasks request for smaller numbers of processors.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {4},
pages = {155-166},
url = {http://www.dmtcs.org/volumes/abstracts/dm030403.abs.html}
}
@Article{DMTCS-030404,
author = {Andrzej Proskurowski and Jan Arne Telle},
title = {Classes of graphs with restricted interval models},
keywords = {Interval graphs, Pathwidth, Bandwidth},
abstract = {We introduce {${q}$}-proper interval graphs as interval graphs with interval models in which
no interval is properly contained in more than {${q}$} other intervals,
and also provide a forbidden induced subgraph characterization of
this class of graphs.
We initiate a graph-theoretic study of subgraphs of {${q}$}-proper
interval graphs with maximum clique size {${k+1}$} and give
an equivalent characterization of these graphs
by restricted path-decomposition.
By allowing the parameter {${q}$} to vary from {${0}$} to {${k}$}, we obtain
a nested hierarchy of graph families,
from graphs of bandwidth at most {${k}$} to graphs of pathwidth at most
{${k}$}.
Allowing both parameters to vary, we have an infinite lattice of graph
classes ordered by containment. },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {4},
pages = {167-176},
url = {http://www.dmtcs.org/volumes/abstracts/dm030404.abs.html}
}
@Article{DMTCS-030405,
author = {Nathalie Caspard},
title = {A characterization for all interval doubling schemes of the lattice of permutations},
keywords = {Permutations, lattice, bounded lattice, interval doubling schemes, arrow relations, linear extension, tableaux},
abstract = {The lattice {${\textbf{S}_{n}}$} of all permutations on a {${n}$}-element set has been shown to be
\emph{bounded} [CAS], which is a strong constructive
property characterized by the fact that
{${\textbf{S}_{n}}$} admits what we call an \emph{ interval
doubling scheme}. In this paper we characterize all interval
doubling schemes of the lattice {${\textbf{S}_{n}}$}, a
result that gives a nice precision on the bounded nature of the
lattice of permutations. This theorem is a direct corollary of two
strong properties that are also given with their proofs.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {4},
pages = {177-188},
url = {http://www.dmtcs.org/volumes/abstracts/dm030405.abs.html}
}
@Article{DMTCS-030406,
author = {Herbert S. Wilf},
title = {Accelerated series for universal constants, by the {W}{Z} method},
keywords = {WZ theory, series convergence, hypergeometric series},
abstract = {In this paper, the author presents a method, based on WZ theory, for finding rapidly converging series for universal constants. This method is
analogous but different from Amdeberhan and Zeilberger's method.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {4},
pages = {189-192},
url = {http://www.dmtcs.org/volumes/abstracts/dm030406.abs.html}
}
@Article{DMTCS-030407,
author = {Ralf Hinze},
title = {Polytypic Functions Over Nested Datatypes},
keywords = {Functional programming, generic programming, nested datatypes, rational trees, reductions.},
abstract = {The theory and practice of polytypic programming is intimately connected with the initial algebra semantics of datatypes. This is both
a blessing and a curse. It is a blessing because the underlying theory
is beautiful and well developed. It is a curse because the initial
algebra semantics is restricted to so-called regular datatypes. Recent
work by R.\ Bird and L.\ Meertens [3] on the semantics
of non-regular or nested datatypes suggests that an extension to
general datatypes is not entirely straightforward. Here we propose an
alternative that extends polytypism to arbitrary datatypes, including
nested datatypes and mutually recursive datatypes. The central idea is
to use rational trees over a suitable set of functor symbols as type
arguments for polytypic functions. Besides covering a wider range of
types the approach is also simpler and technically less involving than
previous ones. We present several examples of polytypic functions,
among others polytypic reduction and polytypic equality. The
presentation assumes some background in functional and in polytypic
programming. A basic knowledge of monads is required for some of the
examples.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 1999,
volume = {3},
number = {4},
pages = {193-214},
url = {http://www.dmtcs.org/volumes/abstracts/dm030407.abs.html}
}
@Article{DMTCS-040101,
author = {Jean-Paul Allouche and Jeffrey Shallit},
title = {Sums of Digits, Overlaps, and Palindromes},
keywords = {sum of digits, overlap-free sequence, palindrome},
abstract = {Let {${s_{k}(n)}$} denote the sum of the digits in the base-{${k}$} representation of {${n}$}. In
a celebrated paper, Thue showed that the infinite word
{${(s_{2}(n) \bmod 2)_{n\ge 0}}$} is
\emph{overlap-free}, i.e., contains no subword of the form
{${axaxa}$} where {${x}$} is any finite word and
{${a}$} is a single symbol. Let {${k,m}$} be integers
with {${k>2}$}, {${m\ge 1}$}. In this paper,
generalizing Thue's result, we prove that the infinite word
{${t_{k,m} := (s_{k}(n) \bmod
m)_{n\ge 0}}$}
is overlap-free if and only if {${m\ge k}$}. We also prove
that {${t_{k,m}}$} contains arbitrarily long squares
(i.e., subwords of the form {${xx}$} where {${x}$} is
nonempty), and contains arbitrarily long palindromes if and only if
{${m\le 2}$}.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2000,
volume = {4},
number = {1},
pages = {1-10},
url = {http://www.dmtcs.org/volumes/abstracts/dm040101.abs.html}
}
@Article{DMTCS-040102,
author = {Alexandre Boudet},
title = {Unification of Higher-order Patterns modulo Simple Syntactic Equational Theories},
keywords = {Unification, Higher-order unification},
abstract = {We present an algorithm for unification of higher-order patterns modulo simple syntactic equational theories as defined by
Kirchner [14]. The algorithm by Miller [17] for pattern unification,
refined by Nipkow [18] is first modified in order to behave as a
first-order unification algorithm. Then the mutation rule for
syntactic theories of Kirchner [13,14] is adapted to pattern
{${E}$}-unification. If the syntactic algorithm for a theory
{${E}$} terminates in the first-order case, then our algorithm
will also terminate for pattern {${E}$}-unification. The result
is a DAG-solved form plus some equations of the form
{${\lambda \overline{x}.F(\overline{x}) =
\lambda
\overline{x}. F(\overline{x^{\pi }})}$}
where {${\overline{x^{\pi }}}$} is a
permutation of {${\overline{x}}$} When all function
symbols are decomposable these latter equations can be discarded,
otherwise the compatibility of such equations with the solved form
remains open.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2000,
volume = {4},
number = {1},
pages = {11-30},
url = {http://www.dmtcs.org/volumes/abstracts/dm040102.abs.html}
}
@Article{DMTCS-040103,
author = {Barcucci, Elena and Del Lungo, Alberto and Pergola, Elisa and Pinzani, Renzo},
title = {Permutations avoiding an increasing number of length-increasing forbidden subsequences},
keywords = {Permutations, Forbidden subsequences, Catalan numbers, Schr{\"o}der numbers},
abstract = {A permutation {${\pi }$} is said to be {${\tau }$}-avoiding if it does not contain any subsequence having all the same pairwise comparisons as
{${\tau }$}.
This paper concerns the characterization and enumeration of permutations which
avoid a set {${F^{j}}$} of subsequences increasing both in number and in length
at the same time. Let {${F^{j}}$} be the set of subsequences of the form
{${\sigma (j+1)(j+2)}$}, {${\sigma }$} being any permutation on
{${\{1,...,j\}}$}.
For {${j=1}$} the only subsequence in {${F^{1}}$} is {${123}$} and the
{${123}$}-avoiding permutations are enumerated by the Catalan numbers; for
{${j=2}$} the subsequences in {${F^{2}}$} are {${1234}$} {${2134}$} and the
{${(1234,2134)}$}avoiding permutations are enumerated by the Schr{\"o}der
numbers; for each other value of {${j}$} greater than {${2}$} the
subsequences in {${F^{j}}$} are {${j!}$} and their length is {${(j+2)}$} the
permutations avoiding these {${j!}$} subsequences are enumerated by a number
sequence
{${\{a_{n}\}}$} such that {${C_{n} \le a_{n} \le n!}$}, {${C_{n}}$} being
the {${n}$}th Catalan number.
For each {${j}$} we determine the generating function of permutations
avoiding the subsequences in {${F^{j}}$} according to the length, to the number
of left minima and of non-inversions.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2000,
volume = {4},
number = {1},
pages = {31-44},
url = {http://www.dmtcs.org/volumes/abstracts/dm040103.abs.html}
}
@Article{DMTCS-040104,
author = {Ross M. McConnell and Jeremy P. Spinrad},
title = {Ordered Vertex Partitioning},
keywords = {Modular Decomposition, Substitution Decomposition, Transitive Orientation},
abstract = {A transitive orientation of a graph is an orientation of the edges that produces a transitive digraph. The modular decomposition
of a graph is a canonical representation of all of its modules.
Finding a transitive orientation and finding the modular decomposition
are in some sense dual problems.
In this paper, we describe a simple {${O(n + m \log n)}$} algorithm that
uses this duality to find both a transitive orientation and the
modular decomposition.
Though the running time is not optimal, this algorithm
is much simpler than any previous algorithms that are not {${\Omega (n^{2})}$}.
The best known time bounds for the problems are {${O(n+m)}$} but they
involve sophisticated techniques.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2000,
volume = {4},
number = {1},
pages = {45-60},
url = {http://www.dmtcs.org/volumes/abstracts/dm040104.abs.html}
}
@Article{DMTCS-040105,
author = {Klaus Dohmen},
title = {Improved inclusion-exclusion identities via closure operators},
keywords = {Inclusion-Exclusion, Sieve Formula, Closure Operator, Convex Geometry, Broken Circuit, Reliability},
abstract = {Let {${(A_{v})_{v {\in} V}}$} be a finite family of sets. We establish an improved inclusion-exclusion
identity for each closure operator on the power set of {${V}$}
having the unique base property. The result generalizes three
improvements of the inclusion-exclusion principle as well as Whitney's
broken circuit theorem on the chromatic polynomial of a graph.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2000,
volume = {4},
number = {1},
pages = {61-66},
url = {http://www.dmtcs.org/volumes/abstracts/dm040105.abs.html}
}
@Article{DMTCS-040106,
author = {Toufik Mansour and Alek Vainshtein},
title = {Avoiding maximal parabolic subgroups of {${S_{k}}$}},
keywords = {permutations, forbidden patterns, parabolic subgroups, Laguerre polynomials, rook polynomials},
abstract = {We find an explicit expression for the generating function of the number of permutations in {${S_{n}}$} avoiding a
subgroup of {${S_{k}}$} generated by all but one simple
transpositions. The generating function turns out to be rational, and
its denominator is a rook polynomial for a rectangular board.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2000,
volume = {4},
number = {1},
pages = {81-90},
url = {http://www.dmtcs.org/volumes/abstracts/dm040106.abs.html}
}
@Article{DMTCS-040201,
author = {Anna Bernasconi},
title = {On a hierarchy of {Boolean} functions hard to compute in constant depth},
keywords = {Boolean functions, {${AC^{0}}$} circuits, size complexity, harmonic analysis},
abstract = {Any attempt to find connections between mathematical properties and complexity has a strong relevance
to the field of Complexity Theory.
This is due to the lack of mathematical techniques to prove lower
bounds for general models of computation.\par
This work represents a step in this direction: we define a combinatorial
property that makes Boolean functions ``\emph{hard}'' to compute in constant depth
and show how the harmonic analysis on the hypercube can be
applied to derive new lower bounds on the size complexity of
previously unclassified Boolean functions.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {4},
number = {2},
pages = {79-90},
url = {http://www.dmtcs.org/volumes/abstracts/dm040201.abs.html}
}
@Article{DMTCS-040202,
author = {Johannes Grassberger and G{\"u}nther H{\"o}rmann},
title = {A note on representations of the finite {Heisenberg} group and sums of greatest common divisors},
keywords = {Heisenberg group, representation of finite groups, sums of gcds},
abstract = {We review an elementary approach to the construction of all irreducible representations of the finite Heisenberg group.
Determining the number of inequivalent
classes of irreducible representations by different methods leads to an
identity of sums involving greatest common divisors. We show how this
identity can be generalized and derive an explicit formula for the sums. },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {4},
number = {2},
pages = {91-100},
url = {http://www.dmtcs.org/volumes/abstracts/dm040202.abs.html}
}
@Article{DMTCS-040203,
author = {Roberto Mantaci and Fanja Rakotondrajao},
title = {A permutations representation that knows what "{E}ulerian" means},
keywords = {Permutations, subexceedant functions, exceedances, Eulerian numbers, derangements, parity of a permutaion},
abstract = {Eulerian numbers (and ``Alternate Eulerian numbers'') are often interpreted as distributions of statistics defined over the
Symmetric group. The main purpose of this paper is to define a way to
represent permutations that provides some other combinatorial
interpretations of these numbers. This representation uses a
one-to-one correspondence between permutations and the so-called \emph{subexceedant functions}.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {4},
number = {2},
pages = {101-108},
url = {http://www.dmtcs.org/volumes/abstracts/dm040203.abs.html}
}
@Article{DMTCS-040204,
author = {Ch\'{\i}nh T. Ho{\`a}ng and Van Bang Le},
title = {{${P_{4}}$}-Colorings and {${P_{4}}$}-Bipartite Graphs},
keywords = {Perfect graph, the Strong Perfect Graph Conjectrue, graph partition, cograph, NP-completeness},
abstract = {A vertex partition of a graph into disjoint subsets {${V_{i}}$}s is said to be a
{${P_{4}}$}-free coloring if each color class
{${V_{i}}$} induces a subgraph without chordless path
on four vertices (denoted by {${P_{4}}$}). Examples of
{${P_{4}}$}-free 2-colorable graphs (also called
{${P_{4}}$}-bipartite graphs) include parity graphs and
graphs with ``few'' {${P_{4}}$}s like
{${P_{4}}$}-reducible and
{${P_{4}}$}-sparse graphs. We prove that, given
{${k\ge 2}$}, \emph{{${P_{4}}$}-Free
{${k}$}-Colorability} is NP-complete even for
comparability graphs, and for {${P_{5}}$}-free
graphs. We then discuss the recognition, perfection and the Strong
Perfect Graph Conjecture (SPGC) for
{${P_{4}}$}-bipartite graphs with special
{${P_{4}}$}-structure. In particular, we show that the
SPGC is true for {${P_{4}}$}-bipartite graphs with one
{${P_{3}}$}-free color class meeting every
{${P_{4}}$} at a midpoint.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {4},
number = {2},
pages = {109-122},
url = {http://www.dmtcs.org/volumes/abstracts/dm040204.abs.html}
}
@Article{DMTCS-040205,
author = {Eugene Curtin},
title = {Cubic {Cayley} graphs with small diameter.},
keywords = {Cayley graph, cubic graph, diameter, Polya's Theorem, permutation group.},
abstract = {In this paper we apply Polya's Theorem to the problem of enumerating Cayley graphs on permutation groups up to
isomorphisms induced by conjugacy in the symmetric group. We
report the results of a search of all three-regular Cayley graphs
on permutation groups of degree at most nine for small diameter
graphs. We explore several methods of constructing covering
graphs of these Cayley graphs. Examples of large graphs with
small diameter are obtained. },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {4},
number = {2},
pages = {123-132},
url = {http://www.dmtcs.org/volumes/abstracts/dm040205.abs.html}
}
@Article{DMTCS-040206,
author = {C. R. Subramanian},
title = {Paths of specified length in random {${k}$}-partite graphs},
keywords = {random graphs, paths, bijections},
abstract = {Fix positive integers {${k}$} and {${l}$}. Consider a random {${k}$}-partite graph on
{${n}$} vertices obtained by partitioning the vertex set into
{${V_{i}, (i=1, {\ldots},k)}$} each having size
{${\Omega (n)}$} and choosing each possible edge with
probability {${p}$}. Consider any vertex {${x}$} in any
{${V_{i}}$} and any vertex {${y}$}. We show that
the expected number of simple paths of even length {${l}$}
between {${x}$} and {${y}$} differ significantly
depending on whether {${y}$} belongs to the same
{${V_{i}}$} (as {${x}$} does) or not. A similar
phenomenon occurs when {${l}$} is odd. This result holds even
when {${k,l}$} vary slowly with {${n}$}. This fact has
implications to coloring random graphs. The proof is based on
establishing bijections between sets of paths.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {4},
number = {2},
pages = {133-138},
url = {http://www.dmtcs.org/volumes/abstracts/dm040206.abs.html}
}
@Article{DMTCS-040207,
author = {Nir Menakerman and Raphael Rom},
title = {Analysis of Transmissions Scheduling with Packet Fragmentation},
keywords = {scheduling, bin packing, algorithm, average case analysis, CATV, fragmentation},
abstract = {We investigate a scheduling problem in which packets, or datagrams, may be fragmented. While there are a few applications to
scheduling with datagram fragmentation, our model of the problem is
derived from a scheduling problem present in data over CATV
networks. In the scheduling problem datagrams of variable lengths must
be assigned (packed) into fixed length time slots. One of the
capabilities of the system is the ability to break a datagram into
several fragments. When a datagram is fragmented, extra bits are added
to the original datagram to enable the reassembly of all the
fragments. We convert the scheduling problem into the problem of bin
packing with item fragmentation, which we define in the following way:
we are asked to pack a list of items into a minimum number of unit
capacity bins. Each item may be fragmented in which case overhead
units are added to the size of every fragment. The cost associated
with fragmentation renders the problem NP-hard, therefore an
approximation algorithm is needed. We define a version of the
well-known Next-Fit algorithm, capable of fragmenting items, and
investigate its performance. We present both worst case and average
case results and compare them to the case where fragmentation is not
allowed.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {4},
number = {2},
pages = {139-156},
url = {http://www.dmtcs.org/volumes/abstracts/dm040207.abs.html}
}
@Article{DMTCS-040208,
author = {David Krumme and Paraskevi Fragopoulou},
title = {Minimum Eccentricity Multicast Trees},
keywords = {multicast, eccentricity, algorithm, communications, graph, network},
abstract = {We consider the problem of constructing a multicast tree that connects a group of source nodes to a group of sink nodes
(receivers) and minimizes the maximum end-to-end delay between any
pair of source/sink nodes. This is known as the \emph{minimum
eccentricity multicast tree} problem, and is directly related to
the quality of service requirements of real multipoint
applications. We deal directly with the problem in its general form,
meaning that the sets of source and sink nodes need not be overlapping
nor disjoint. The main contribution of this work is a polynomial
algorithm for this problem on general networks which is inspired by an
innovative method that uses geometric relationships on the
{${xy}$}-plane.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {4},
number = {2},
pages = {157-172},
url = {http://www.dmtcs.org/volumes/abstracts/dm040208.abs.html}
}
@Article{DMTCS-040209,
author = {Michel Habib and Christophe Paul and Laurent Viennot},
title = {Linear time recognition of {${P_{4}}$}-indifference graphs},
keywords = {{${P_{4}}$}-indifference, algorithm, recognition},
abstract = {A graph is a {${P_{4}}$}-indifference graph if it admits an ordering {${<}$} on its vertices such that
every chordless path with vertices {${a}$}, {${b}$},
{${c}$}, {${d}$} and edges {${ab}$},
{${bc}$}, {${cd}$} has {${a**4)}$} of vertices be properly edge-colored with
{${n-1}$} colors in such a way that the edges can be
partitioned into edge disjoint colorful isomorphic spanning trees? A
spanning treee is colorful if all {${n-1}$} colors occur among
its edges. It is proved that this is possible to accomplish whenever
{${n}$} is a power of two, or five times a power of two.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2002,
volume = {5},
number = {1},
pages = {121-126},
url = {http://www.dmtcs.org/volumes/abstracts/dm050108.abs.html}
}
@Article{DMTCS-050109,
author = {Luitpold Babel and Andreas Brandst{\"a}dt and Van Bang Le},
title = {Recognizing the {${P_{4}}$}-structure of claw-free graphs and a larger graph class},
keywords = {Claw-free graphs, reconstruction problem, {${P_{4}}$}-structure, {${p}$}-connected graphs, homogeneous set, perfect graphs.},
abstract = {The {${P_{4}}$}-structure of a graph {${G}$} is a hypergraph {${\textbf{H}}$} on the same vertex set such that four vertices
form a hyperedge in {${\textbf{H}}$} whenever they induce a
{${P_{4}}$} in {${G}$}. We present a constructive algorithm
which tests in polynomial time whether a given 4-uniform hypergraph is
the {${P_{4}}$}-structure of a claw-free graph and of
(banner,chair,dart)-free graphs. The algorithm relies on new
structural results for (banner,chair,dart)-free graphs which are based
on the concept of {${p}$}-connectedness. As a byproduct, we obtain a
polynomial time criterion for perfectness for a large class of graphs
properly containing claw-free graphs.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2002,
volume = {5},
number = {1},
pages = {127-146},
url = {http://www.dmtcs.org/volumes/abstracts/dm050109.abs.html}
}
@Article{DMTCS-050110,
author = {Elias Dahlhaus and Jens Gustedt and Ross M. McConnell},
title = {Partially Complemented Representations of Digraphs},
keywords = {efficient graph algorithms, data structures, search strategies, modular decomposition},
abstract = {A \emph{complementation operation} on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs
into arcs. This defines an equivalence relation where two digraphs
are equivalent if one can be obtained from the other by a sequence of
such operations. We show that given an adjacency-list representation
of a digraph {${G}$}, many fundamental graph algorithms can be
carried out on any member {${G'}$} of {${G}$}'s
equivalence class in {${O(n+m)}$} time, where {${m}$} is
the number of arcs in {${G}$}, not the number of arcs in
{${G'}$}. This may have advantages when {${G'}$} is
much larger than {${G}$}. We use this to generalize to
digraphs a simple {${O(n + m \log n)}$} algorithm of McConnell
and Spinrad for finding the modular decomposition of undirected
graphs. A key step is finding the strongly-connected components of a
digraph {${F}$} in {${G}$}'s equivalence class, where
{${F}$} may have {${\omega (m \log n)}$} arcs.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2002,
volume = {5},
number = {1},
pages = {147-168},
url = {http://www.dmtcs.org/volumes/abstracts/dm050110.abs.html}
}
@Article{DMTCS-050111,
author = {John Ellis and Hongbing Fan and Jeffrey Shallit},
title = {The Cycles of the Multiway Perfect Shuffle Permutation },
keywords = {perfect shuffle permutation, cycle decomposition},
abstract = {The {${(k,n)}$}-perfect shuffle, a generalisation of the 2-way perfect shuffle, cuts a deck of {${kn}$} cards into
{${k}$} equal size decks and interleaves them perfectly with
the first card of the last deck at the top, the first card of the
second-to-last deck as the second card, and so on. It is formally
defined to be the permutation
{${\rho _{k,n}:\ i\ {\rightarrow}\ ki\ \bmod (kn+1)}$}, for {${1 \le i \le kn}$}. We uncover the cycle
structure of the {${(k,n)}$}-perfect shuffle permutation by a
group-theoretic analysis and show how to compute representative
elements from its cycles by an algorithm using {${O(kn)}$} time
and {${O((\log kn)^{2})}$} space. Consequently it is possible to
realise the {${(k,n)}$}-perfect shuffle via an in-place,
linear-time algorithm. Algorithms that accomplish this for the 2-way
shuffle have already been demonstrated.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2002,
volume = {5},
number = {1},
pages = {169-180},
url = {http://www.dmtcs.org/volumes/abstracts/dm050111.abs.html}
}
@Article{DMTCS-050112,
author = {W. M. B. Dukes},
title = {On a Unimodality Conjecture in Matroid Theory},
keywords = {Matroid Theory, Unimodality Conjecture, Rank-2 matroids, Rank-3 matroids},
abstract = {A certain unimodal conjecture in matroid theory states the number of rank-{${r}$} matroids on a set of size {${n}$}
is unimodal in {${r}$} and attains its maximum at
{${r=\lfloor n/2 \rfloor }$}. We show that this conjecture holds
up to {${r=3}$} by constructing a map from a class of rank-2
matroids into the class of loopless rank-3 matroids. Similar
inequalities are proven for the number of non-isomorphic loopless
matroids, loopless matroids and matroids.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2002,
volume = {5},
number = {1},
pages = {181-190},
url = {http://www.dmtcs.org/volumes/abstracts/dm050112.abs.html}
}
@Article{DMTCS-050113,
author = {J. L. Dornstetter and D. Krob and J. Y. Thibon and E. A. Vassilieva},
title = {Performance analysis of demodulation with diversity -- A combinatorial approach {I}: Symmetric function theoretical methods},
keywords = {Symmetric functions; Schur functions; Telecommunications},
abstract = {This paper is devoted to the presentation of a combinatorial approach, based on the theory of symmetric functions, for analyzing
the performance of a family of demodulation methods used in mobile
telecommunications.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2002,
volume = {5},
number = {1},
pages = {191-204},
url = {http://www.dmtcs.org/volumes/abstracts/dm050113.abs.html}
}
@Article{DMTCS-050114,
author = {Fountoulakis, Nikolaos and McDiarmid, Colin},
title = {Upper bounds on the non-{${3}$}-colourability threshold of random graphs},
keywords = {sparse random graphs, 3-colourability, thresholds},
abstract = {We present a full analysis of the expected number of `rigid' 3-colourings of a sparse random graph. This shows that, if the
average degree is at least {${4.99}$}, then as {${n {\rightarrow}
{\infty}}$} the expected number of such colourings tends to
{${0}$} and so the probability that the graph is
{${3}$}-colourable tends to {${0}$}. (This result is tight, in that
with average degree {${4.989}$} the expected number tends to {${{\infty}}$}.) This
bound appears independently in Kaporis \textit{et al.}\ [Kap]. We
then give a minor improvement, showing that the probability that the
graph is {${3}$}-colourable tends to {${0}$} if the average degree is at least
{${4.989}$}.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2002,
volume = {5},
number = {1},
pages = {205-226},
url = {http://www.dmtcs.org/volumes/abstracts/dm050114.abs.html}
}
@Article{DMTCS-050115,
author = {Fr{\'e}d{\'e}ric Saubion and Igor St{\'e}phan},
title = {A Unified Framework to Compute over Tree Synchronized Grammars and Primal Grammars},
keywords = {Tree Grammars ; Proof Systems ; Prolog Implementation},
abstract = {Tree languages are powerful tools for the representation and schematization of infinite sets of terms for various purposes
(unification theory, verification and specification ...). In order to
extend the regular tree language framework, more complex formalisms
have been developed. In this paper, we focus on Tree Synchronized
Grammars and Primal Grammars which introduce specific control
structures to represent non regular sets of terms. We propose a common
unified framework in order to achieve the membership test for these
particular languages. Thanks to a proof system, we provide a full
operational framework, that allows us to transform tree grammars into
Prolog programs (as it already exists for word grammars with DCG)
whose goal is to recognize terms of the corresponding language.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2002,
volume = {5},
number = {1},
pages = {227-262},
url = {http://www.dmtcs.org/volumes/abstracts/dm050115.abs.html}
}
@Article{DMTCS-060101,
author = {Alexander Burstein and Toufik Mansour},
title = {Counting occurrences of some subword patterns},
keywords = {Generalized patterns, subword patterns},
abstract = {We find generating functions the number of strings (words) containing a specified number of occurrences of certain types of
order-isomorphic classes of substrings called subword patterns. In
particular, we find generating functions for the number of strings
containing a specified number of occurrences of a given {${3}$}-letter
subword pattern.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {6},
number = {1},
pages = {1-12},
url = {http://www.dmtcs.org/volumes/abstracts/dm060101.abs.html}
}
@Article{DMTCS-060102,
author = {Chauve, Cedric},
title = {A bijection between planar constellations and some colored {L}agrangian trees},
keywords = {Planar maps, trees, enumeration, bijection, Lagrange formula},
abstract = {Constellations are colored planar maps that generalize different families of maps (planar maps, bipartite planar maps,
bi-Eulerian planar maps, planar cacti, ...) and are strongly related
to factorizations of permutations. They were recently studied by
Bousquet-M{\'e}lou and Schaeffer who describe a correspondence between
these maps and a family of trees, called Eulerian trees. In this
paper, we derive from their result a relationship between planar
constellations and another family of trees, called stellar trees. This
correspondence generalizes a well known result for planar cacti, and
shows that planar constellations are colored Lagrangian objects (that
is objects that can be enumerated by the Good-Lagrange formula). We
then deduce from this result a new formula for the number of planar
constellations having a given face distribution, different from the
formula one can derive from the results of Bousquet-M{\'e}lou and
Schaeffer, along with systems of functional equations for the
generating functions of bipartite and bi-Eulerian planar maps
enumerated according to the partition of faces and vertices.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {6},
number = {1},
pages = {13-40},
url = {http://www.dmtcs.org/volumes/abstracts/dm060102.abs.html}
}
@Article{DMTCS-060103,
author = {Vince Grolmusz},
title = {A Note on Set Systems with no Union of Cardinality {${0}$} modulo {${m}$}},
keywords = {hypergraphs, composite modulus, explicit constructions},
abstract = {\emph{Alon, Kleitman, Lipton, Meshulam, Rabin} and \emph{Spencer} (Graphs. Combin. 7 (1991), no. 2, 97-99) proved, that
for any hypergraph
{${\textbf{\textit{F}}=\{F_{1},F_{2},{\ldots},
F_{d(q-1)+1}\}}$}, where {${q}$} is a prime-power,
and {${d}$} denotes the maximal degree of the hypergraph, there
exists an {${\textbf{\textit{F}}_{0}{\subset}
\textbf{\textit{F}}}$}, such that
{${|\bigcup_{F{\in}\textbf{\textit{F}}_{0}}F|
\equiv 0 (q)}$}. We give a direct, alternative proof for this
theorem, and we also show that an explicit construction exists for a
hypergraph of degree {${d}$} and size
{${\Omega (d^{2})}$} which does not contain a non-empty
sub-hypergraph with a union of size 0 modulo 6, consequently, the
theorem does not generalize for non-prime-power moduli.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {6},
number = {1},
pages = {41-44},
url = {http://www.dmtcs.org/volumes/abstracts/dm060103.abs.html}
}
@Article{DMTCS-060104,
author = {Brice Effantin and Hamamache Kheddouci},
title = {The {${b}$}-chromatic number of power graphs},
keywords = {coloring, b-chromatic number, power graph, path, cycle and complete binary tree.},
abstract = {The {${b}$}-chromatic number of a graph {${G}$} is defined as the maximum number {${k}$} of
colors that can be used to color the vertices of {${G}$}, such
that we obtain a proper coloring and each color {${i}$}, with
{${1 \le i\le k}$}, has at least one representant
{${x_{i}}$} adjacent to a vertex of every color
{${j}$}, {${1 \le j \ne i \le k}$}. In this paper, we
discuss the {${b}$}-chromatic number of some power graphs. We
give the exact value of the {${b}$}-chromatic number of power
paths and power complete binary trees, and we bound the
{${b}$}-chromatic number of power cycles.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {6},
number = {1},
pages = {45-54},
url = {http://www.dmtcs.org/volumes/abstracts/dm060104.abs.html}
}
@Article{DMTCS-060105,
author = {Johann Cigler},
title = {Some Algebraic Aspects of {Morse} Code Sequences},
keywords = {Fibonacci polynomial, {${q}$}-analogue, {${q}$}-binomial coefficient},
abstract = {Morse code sequences are very useful to give combinatorial interpretations of various properties of Fibonacci numbers. In this
note we study some algebraic and combinatorial aspects of Morse code
sequences and obtain several {${q}$}-analogues of Fibonacci
numbers and Fibonacci polynomials and their generalizations.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {6},
number = {1},
pages = {55-68},
url = {http://www.dmtcs.org/volumes/abstracts/dm060105.abs.html}
}
@Article{DMTCS-060106,
author = {Klaus Dohmen and Andr{\'e} Poenitz and Peter Tittmann},
title = {A new two-variable generalization of the chromatic polynomial},
keywords = {chromatic polynomial, set partition, broken circuit, pathwidth, chromatic symmetric function},
abstract = {We present a two-variable polynomial, which simultaneously generalizes the chromatic polynomial, the independence polynomial, and
the matching polynomial of a graph. This new polynomial satisfies
both an edge decomposition formula and a vertex decomposition formula.
We establish two general expressions for this new polynomial: one in
terms of the broken circuit complex and one in terms of the lattice of
forbidden colorings. We show that the new polynomial may be
considered as a specialization of Stanley's chromatic symmetric
function. We finally give explicit expressions for the generalized
chromatic polynomial of complete graphs, complete bipartite graphs,
paths, and cycles, and show that it can be computed in polynomial time
for trees and graphs of restricted pathwidth.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {6},
number = {1},
pages = {69-90},
url = {http://www.dmtcs.org/volumes/abstracts/dm060106.abs.html}
}
@Article{DMTCS-060107,
author = {Charles Knessl},
title = {Numerical Studies of the Asymptotic Height Distribution in Binary Search Trees},
keywords = {asymptotics, height, binary search trees, numerical analysis},
abstract = {We study numerically a non-linear integral equation that arises in the study of binary search trees. If the tree is
constructed from {${n}$} elements, this integral equation describes the
asymptotic (as {${n{\rightarrow}{\infty}}$}) distribution of the height of the tree.
This supplements some asymptotic results we recently obtained for the
tails of the distribution. The asymptotic height distribution is
shown to be unimodal with highly asymmetric tails.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {6},
number = {1},
pages = {91-100},
url = {http://www.dmtcs.org/volumes/abstracts/dm060107.abs.html}
}
@Article{DMTCS-060108,
author = {Peter Paule and Helmut Prodinger},
title = {Fountains, histograms, and {${q}$}-identities},
keywords = {{${q}$}--identities, fountains, histograms, Schur polynomials},
abstract = {We solve the recursion {${S_{n}=S_{n-1}-q^{n}S_{n-p}}$},
both, explicitly, and in the limit for {${n{\rightarrow}{\infty}}$},
proving in this way a formula due to Merlini and Sprugnoli. It is also
discussed how computer algebra could be applied.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {6},
number = {1},
pages = {101-106},
url = {http://www.dmtcs.org/volumes/abstracts/dm060108.abs.html}
}
@Article{DMTCS-060109,
author = {Wei-Mei Chen and Hsien-Kuei Hwang and Tsung-Hsi Tsai},
title = {Efficient maxima-finding algorithms for random planar samples},
keywords = {maxima, average-case analysis, sequential algorithms, sieve algorithms},
abstract = {We collect major known algorithms in the literature for finding the maxima of multi-dimensional points and provide a simple
classification. Several new algorithms are proposed. In particular, we
give a new maxima-finding algorithm with expected complexity
{${n+O(\sqrt{n\log n})}$} when the input is a sequence of points
uniformly chosen at random from general planar regions. We also give a
sequential algorithm, very efficient for practical purposes.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {6},
number = {1},
pages = {107-122},
url = {http://www.dmtcs.org/volumes/abstracts/dm060109.abs.html}
}
@Article{DMTCS-060110,
author = {Selma Djelloul and Mekkia Kouider},
title = {Minimum survivable graphs with bounded distance increase},
keywords = {distance, fault-tolerance, spanning subgraph},
abstract = {We study in graphs properties related to fault-tolerance in case a node fails. A graph {${G}$} is
{${k}$}-self-repairing, where {${k}$} is a non-negative
integer, if after the removal of any vertex no distance in the
surviving graph increases by more than {${k}$}. In the design
of interconnection networks such graphs guarantee good fault-tolerance
properties. We give upper and lower bounds on the minimum number of
edges of a {${k}$}-self-repairing graph for prescribed
{${k}$} and {${n}$}, where {${n}$} is the order
of the graph. We prove that the problem of finding, in a
{${k}$}-self-repairing graph, a spanning
{${k}$}-self-repairing subgraph of minimum size is NP-Hard.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {6},
number = {1},
pages = {123-132},
url = {http://www.dmtcs.org/volumes/abstracts/dm060110.abs.html}
}
@Article{DMTCS-060111,
author = {Andreas Weiermann},
title = {An application of results by {H}ardy, {R}amanujan and {K}aramata to
{A}ckermannian functions},
keywords = {Ackermann function, Karamata's theorem, Hardy Ramanujan methods, analytic combinatorics},
abstract = {The Ackermann function is a fascinating and well studied paradigm for a function which eventually dominates all primitive
recursive functions. By a classical result from the theory of
recursive functions it is known that the Ackermann function can be
defined by an unnested or descent recursion along the segment of
ordinals below {${\omega ^{\omega }}$} (or equivalently
along the order type of the polynomials under eventual domination). In
this article we give a fine structure analysis of such a Ackermann
type descent recursion in the case that the ordinals below
{${\omega ^{\omega }}$} are represented via a Hardy
Ramanujan style coding. This paper combines number-theoretic results
by Hardy and Ramanujan, Karamata's celebrated Tauberian theorem and
techniques from the theory of computability in a perhaps surprising
way.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {6},
number = {1},
pages = {133-142},
url = {http://www.dmtcs.org/volumes/abstracts/dm060111.abs.html}
}
@Article{DMTCS-060201,
author = {Narjes Berregeb and Riadh Robbana and Ashish Tiwari},
title = {Towards automated proofs of observational properties},
keywords = {observational, contexts, rewriting},
abstract = {Observational theories are a generalization of first-order theories where two objects are observationally equal if they cannot be
distinguished by experiments with observable results. Such
experiments, called contexts, are usually infinite. Therfore, we
consider a special finite set of contexts, called cover-contexts,
``\emph{covering}'' all the observable contexts. Then, we show that
to prove that two objects are observationally equal, it is sufficient
to prove that they are equal (in the classical sense) under these
cover-contexts. We give methods based on rewriting techniques, for
constructing such cover-contexts for interesting classes of
observational specifications.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {143-162},
url = {http://www.dmtcs.org/volumes/abstracts/dm060201.abs.html}
}
@Article{DMTCS-060202,
author = {Caspard, Nathalie and Monjardet, Bernard},
title = {Some lattices of closure systems on a finite set},
keywords = {Anti-exchange closure operator, closure system, convex geometry, (locally distributive) lattice, quasi-closed set.},
abstract = {In this paper we study two lattices of significant particular closure systems on a finite set, namely the union stable
closure systems and the convex geometries. Using the notion of
(admissible) quasi-closed set and of (deletable) closed set, we
determine the covering relation {${{\prec}}$} of these lattices
and the changes induced, for instance, on the irreducible elements
when one goes from {${C}$} to {${C'}$} where
{${C}$} and {${C'}$} are two such closure systems
satisfying {${C {\prec} C'}$}. We also do a systematic study of
these lattices of closure systems, characterizing for instance their
join-irreducible and their meet-irreducible elements.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {163-190},
url = {http://www.dmtcs.org/volumes/abstracts/dm060202.abs.html}
}
@Article{DMTCS-060203,
author = {R{\'e}gnier, Mireille and Denise, Alain},
title = {Rare Events and Conditional Events on Random Strings},
keywords = {large deviations, combinatorics, generating fumctions, words, genome, computable closed formulae. },
abstract = {Some strings -the texts- are assumed to be randomly generated, according to a probability model that is either a Bernoulli
model or a Markov model. A rare event is the over or
under-representation of a word or a set of words. The aim of this
paper is twofold. First, a single word is given. One studies the tail
distribution of the number of its occurrences. Sharp large deviation
estimates are derived. Second, one assumes that a given word is
overrepresented. The distribution of a second word is studied;
formulae for the expectation and the variance are derived. In both
cases, the formulae are accurate and actually computable. These
results have applications in computational biology, where a genome is
viewed as a text.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {191-214},
url = {http://www.dmtcs.org/volumes/abstracts/dm060203.abs.html}
}
@Article{DMTCS-060204,
author = {Vladimir E. Alekseev and Alastair Farrugia and Vadim V. Lozin},
title = {New Results on Generalized Graph Coloring},
keywords = {Generalized Graph Coloring; Polynomial algorithm; NP-completeness},
abstract = {For graph classes {${{\wp}_{1},...,{\wp}_{k}}$}, Generalized Graph Coloring is the problem of deciding whether the vertex set of a given
graph {${G}$} can be partitioned into subsets
{${V_{1},...,V_{k}}$} so that {${V_{j}}$} induces a graph
in the class {${{\wp}_{j}}$} {${(j=1,2,...,k)}$}. If
{${{\wp}_{1}=...={\wp}_{k}}$} is the class of edgeless
graphs, then this problem coincides with
the standard vertex {${k}$}-COLORABILITY,
which is known to be NP-complete for any {${k\ge 3}$}.
Recently, this result has been generalized by
showing that if all {${{\wp}_{i}}$}'s are additive
hereditary, then the generalized graph coloring
is NP-hard, with the only exception of bipartite
graphs. Clearly, a similar result follows when
all the {${{\wp}_{i}}$}'s are co-additive. },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {215-222},
url = {http://www.dmtcs.org/volumes/abstracts/dm060204.abs.html}
}
@Article{DMTCS-060205,
author = {Eric Babson and Victor Reiner},
title = {Coxeter-like complexes},
keywords = {Coxeter complex, simplicial poset, Boolean complex, chessboard complex, Shephard group, unitary reflection group, simplex of groups, homology representation},
abstract = {Motivated by the Coxeter complex associated to a Coxeter system {${(W,S)}$}, we introduce a simplicial regular cell
complex {${\Delta (G,S)}$} with a {${G}$}-action
associated to any pair {${(G,S)}$} where {${G}$} is a
group and {${S}$} is a finite set of generators for
{${G}$} which is minimal with respect to inclusion. We examine
the topology of {${\Delta (G,S)}$}, and in particular the
representations of {${G}$} on its homology groups. We look
closely at the case of the symmetric group {${S_{n}}$}
minimally generated by (not necessarily adjacent) transpositions, and
their type-selected subcomplexes. These include not only the Coxeter
complexes of type {${A}$}, but also the well-studied chessboard
complexes.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {223-252},
url = {http://www.dmtcs.org/volumes/abstracts/dm060205.abs.html}
}
@Article{DMTCS-060206,
author = {Josef Pieprzyk and Xian-Mo Zhang},
title = {On Cheating Immune Secret Sharing},
keywords = {Secret Sharing, Cheating Prevention, Cheating Immune},
abstract = {The paper addresses the cheating prevention in secret sharing. We consider secret sharing with binary shares. The secret
also is binary. This model allows us to use results and constructions
from the well developed theory of cryptographically strong boolean
functions. In particular, we prove that for given secret sharing, the
average cheating probability over all cheating vectors and all
original vectors, i.e.,
{${
1/n 2^{n} \sum _{c=1...n}
\sum _{\alpha {\in}V
{n}}
\rho _{c,\alpha }
}$},
denoted by {${\overline{\rho }}$},
satisfies {${\overline{\rho } \ge
\frac12 }$}, and the equality holds if and only if
{${\rho _{c,\alpha }}$} satisfies {${\rho _{c,\alpha }=
\frac12 }$} for every cheating vector {${\delta _{c}}$} and every
original vector {${\alpha }$}. In this case the secret sharing is said to
be cheating immune. We further establish a relationship between
cheating-immune secret sharing and cryptographic criteria of boolean
functions.This enables us to construct cheating-immune secret sharing.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {253-264},
url = {http://www.dmtcs.org/volumes/abstracts/dm060206.abs.html}
}
@Article{DMTCS-060207,
author = {Honkala, Iiro and Laihonen, Tero and Ranto, Sanna},
title = {On Locating-Dominating Codes in Binary {Hamming} Spaces},
keywords = {Locating-dominating codes, Hamming space, Identifying codes},
abstract = {Locating faulty processors in a multiprocessor system gives the motivation for locating-dominating codes. We consider these codes
in binary hypercubes and generalize the concept for the situation in
which we want to locate more than one malfunctioning processor.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {265-282},
url = {http://www.dmtcs.org/volumes/abstracts/dm060207.abs.html}
}
@Article{DMTCS-060208,
author = {Fr{\'e}d{\'e}ric Chazal and V{\'e}ronique Maume-Deschamps},
title = {Statistical properties of general {M}arkov dynamical sources: applications to information theory},
keywords = {dynamical sources, information theory, transfer operator, Markov sources},
abstract = {In \textit{Dynamical sources in information theory: fundamental intervals and word prefixes}, B. Vall{\'e}e studies statistical
properties of words generated by dynamical sources. This is done using
generalized Ruelle operators. The aim of this article is to generalize
sources for which the results hold. First, we avoid the use of
Grotendieck theory and Fredholm determinants, this allows dynamical
sources that cannot be extended to a complex disk or that are not
analytic. Second, we consider Markov sources: the language generated
by the source over an alphabet {${\textbf{M}}$} is not
necessarily {${\textbf{M}^{*}}$}.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {283-314},
url = {http://www.dmtcs.org/volumes/abstracts/dm060208.abs.html}
}
@Article{DMTCS-060209,
author = {Karell Bertet and Mirabelle Nebut},
title = {Efficient Algorithms on the Family Associated to an Implicational System},
keywords = {lattice, ordered set, Moore family, implicational system, closure operator, algorithm},
abstract = {An implication system (IS) on a finite set {${S}$} is a set of rules called {${\Sigma }$}-implications of the kind
{${A {\rightarrow}_{\Sigma } B}$}, with {${A,B {\subseteq}
S}$}. A subset {${X {\subseteq} S}$} satisfies {${A
{\rightarrow}_{\Sigma } B}$} when ``{${A {\subseteq} X}$}
implies {${B {\subseteq} X}$}'' holds, so ISs can be used to
describe constraints on sets of elements, such as dependency or
causality. ISs are formally closely linked to the well known notions
of closure operators and Moore families. This paper focuses on their
algorithmic aspects. A number of problems issued from an IS
{${\Sigma }$} (e.g. is it minimal, is a given implication
entailed by the system) can be reduced to the computation of closures
{${\phi _{\Sigma }(X)}$}, where
{${\phi _{\Sigma }}$} is the closure operator
associated to {${\Sigma }$}. We propose a new approach to compute such
closures, based on the characterization of the direct-optimal IS
{${\Sigma _{do}}$} which has the following
properties:
\begin{enumerate}
\item{}it is equivalent to {${\Sigma }$}
\item{}{${\phi _{\Sigma _{do}}(X)}$} (thus
{${\phi _{\Sigma }(X)}$}) can be computed by a single scanning of
{${\Sigma _{do}}$}-implications
\item{}it is of
minimal size with respect to ISs satisfying 1. and 2. \end{enumerate}
We
give algorithms that compute {${\Sigma _{do}}$}, and
from
{${\Sigma _{do}}$} closures
{${\phi _{\Sigma }(X)}$} and the Moore family associated to
{${\phi _{\Sigma }}$}.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {315-338},
url = {http://www.dmtcs.org/volumes/abstracts/dm060209.abs.html}
}
@Article{DMTCS-060210,
author = {Vida Dujmovi{\'c} and David R. Wood},
title = {On Linear Layouts of Graphs},
keywords = {graph layout, graph drawing, stack layout, queue layout, arch layout, book embedding, queue-number, stack-number, page-number, book-thickness},
abstract = {{In a total order of the vertices of a graph, two edges with no endpoint in common can be \emph{crossing}, \emph{nested}, or \emph{disjoint}. A \emph{{${k}$}-stack} (respectively, \emph{{${k}$}-queue}, \emph{{${k}$}-arch}) \emph{layout} of a graph consists of a total order of the vertices, and a partition of the edges into {${k}$} sets of pairwise non-crossing (non-nested, non-disjoint) edges. Motivated by numerous applications, stack layouts (also called \emph{book embeddings}) and queue layouts are widely studied in the literature, while this is the first paper to investigate arch layouts.\par} {Our main result is a characterisation of {${k}$}-arch
graphs as the \emph{almost {${(k+1)}$}-colourable} graphs; that
is, the graphs {${G}$} with a set {${S}$} of at most {${k}$}
vertices, such that {${G \ S}$} is {${(k+1)}$}-colourable.\par} {In addition, we survey the following fundamental questions regarding each type of layout, and in the case of queue layouts, provide simple proofs of a number of existing
results. How does one partition the edges given a fixed ordering of the vertices? What is the maximum number of edges in each type of layout? What is the maximum chromatic number of a graph admitting each type of layout? What is the computational complexity of recognising the graphs that admit each type of layout?\par}
{A comprehensive bibliography of all known references on these topics is included. \par}},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {339-358},
url = {http://www.dmtcs.org/volumes/abstracts/dm060210.abs.html}
}
@Article{DMTCS-060211,
author = {Rajendra M. Pawale},
title = {A Note on {${t}$}-designs with {${t}$} Intersection Numbers},
keywords = {t-design},
abstract = {We discuss Ray-Chaudhari and Wilson inequality for a {${0}$}-design and give simple proof of the result `\emph{For fixed block size {${k}$}, there
exist finitely many parametrically feasible {${t}$}-designs with {${t}$}
intersection numbers and {${\lambda > 1}$}}'.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {359-364},
url = {http://www.dmtcs.org/volumes/abstracts/dm060211.abs.html}
}
@Article{DMTCS-060212,
author = {Carsten Schneider},
title = {The Summation Package Sigma: Underlying Principles and a Rhombus Tiling Application},
keywords = {symbolic summation, rhombus tilings},
abstract = {We give an overview of how a huge class of multisum identities can be proven and discovered with the summation package Sigma implemented in
the computer algebra system Mathematica. General principles of symbolic
summation are discussed.
We illustrate the usage of Sigma by showing how one can find and prove a
multisum identity that arose in the enumeration of rhombus tilings of a
symmetric hexagon. Whereas this identity has been derived alternatively
with the help of highly involved transformations of special functions,
our tools enable to find and prove this identity completely
automatically with the computer.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {365-386},
url = {http://www.dmtcs.org/volumes/abstracts/dm060212.abs.html}
}
@Article{DMTCS-060213,
author = {Drmota, Michael and Gittenberger, Bernhard},
title = {The Width of {G}alton-{W}atson Trees Conditioned by the Size},
keywords = {branching processes, simply generated tree, generating functions, convergence of moments},
abstract = {It is proved that the moments of the width of Galton-Watson trees of size {${n}$} and with offspring variance {${\sigma ^{2}}$} are asymptotically
given by {${(\sigma \sqrt{n})^{p}m_{p}}$} where {${m_{p}}$} are the moments of the maximum of
the local time of a standard scaled Brownian excursion. This is done by
combining a weak limit theorem and a tightness estimate. The method is quite
general and we state some further applications.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {387-400},
url = {http://www.dmtcs.org/volumes/abstracts/dm060213.abs.html}
}
@Article{DMTCS-060214,
author = {Kayll, P. Mark},
title = {Well-spread sequences and edge-labellings with constant Hamilton-weight},
keywords = {Well-spread, weak Sidon, graph labelling, Hamilton cycle},
abstract = {A sequence {${(a_{i})}$} of integers is \emph{well-spread} if the sums {${a_{i}+a_{j}}$}, for {${iGL1,GL2 introduced \emph{freely braided} permutation as a special class of restricted permutations has arisen in representation theory. The freely braided
permutations were introduced and studied as the upper bound for
the number of commutation classes of reduced expressions for an
element of a simply laced Coxeter group is achieved if and only if
when the element is freely braided. In this paper, we prove that
the generating function for the number of freely braided
permutations in {${S_{n}}$} is given by
\par {${(1-3x-2x^{2}+(1+x)\sqrt{1-4x}) / (1-4x-x^{2}+(1-x^{2})\sqrt{1-4x}).}$}\par },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {461-470},
url = {http://www.dmtcs.org/volumes/abstracts/dm060218.abs.html}
}
@Article{DMTCS-060219,
author = {Josef Pieprzyk and Xian-Mo Zhang},
title = {Characterisations of Ideal Threshold Schemes},
keywords = {Secret Sharing, Perfect Threshold Schemes, Ideal Threshold Schemes},
abstract = {We characterise ideal threshold schemes from different approaches. Since the characteristic properties are independent to particular descriptions of threshold schemes all ideal threshold schemes can be examined by new points of view and new results on ideal threshold schemes can be discovered. },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {471-482},
url = {http://www.dmtcs.org/volumes/abstracts/dm060219.abs.html}
}
@Article{DMTCS-060220,
author = {Hon-Chan Chen},
title = {Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs},
keywords = {cut vertex, bridge, trapezoid graph, algorithm},
abstract = {Let G be a graph. A component of G is a maximal connected subgraph in G. A vertex v is a cut vertex of G if k(G-v) > k(G), where k(G) is the number of components in G. Similarly, an edge e is a bridge of G if k(G-e) > k(G). In this paper, we will propose new O(n) algorithms for finding cut vertices and bridges of a trapezoid graph, assuming the trapezoid diagram is given. Our algorithms can be easily parallelized on the EREW PRAM computational model so that cut vertices and bridges can be found in O(log n) time by using O(n / log n) processors. },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {483-496},
url = {http://www.dmtcs.org/volumes/abstracts/dm060220.abs.html}
}
@Article{DMTCS-060221,
author = {Vida Dujmovi{\'c} and Attila P{\'o}r and David R. Wood},
title = {Track Layouts of Graphs},
keywords = {graph layout, graph drawing, track layout, stack layout, queue layout, book embedding, track-number, queue-number, stack-number, page-number, book-thickness, geometric thickness, three-dimensional graph drawing},
abstract = {A \emph{{${(k,t)}$}-track layout} of a graph {${G}$} consists of a (proper) vertex {${t}$}-colouring of {${G}$}, a total order of each vertex colour class, and a (non-proper) edge {${k}$}-colouring such that between each pair of colour classes no two monochromatic edges cross. This structure has recently arisen in the study of three-dimensional graph drawings. This paper presents the beginnings of a theory of track layouts. First we determine the maximum number of edges in a {${(k,t)}$}-track layout, and show how to colour the edges given fixed linear orderings of the vertex colour classes. We then describe methods for the manipulation of track layouts. For example, we show how to decrease the number of edge colours in a track layout at the expense of increasing the number of tracks, and vice versa. We then study the relationship between track layouts and other models of graph layout, namely stack and queue layouts, and geometric thickness. One of our principle results is that the queue-number and track-number of a graph are tied, in the sense that one is bounded by a function of the other. As corollaries we prove that acyclic chromatic number is bounded by both queue-number and stack-number. Finally we consider track layouts of planar graphs. While it is an open problem whether planar graphs have bounded track-number, we prove bounds on the track-number of outerplanar graphs, and give the best known lower bound on the track-number of planar graphs.\\ \ },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {497-522},
url = {http://www.dmtcs.org/volumes/abstracts/dm060221.abs.html}
}
@Article{DMTCS-060222,
author = {Loh, Po-Shen and Schulman, Leonard J.},
title = {Improved Expansion of Random Cayley Graphs},
keywords = {expander graphs, Cayley graphs, second eigenvalue, logarithmic generators},
abstract = {In Random Cayley Graphs and Expanders, N. Alon and Y. Roichman proved that for every {${\epsilon > 0}$}
there is a finite {${c(\epsilon )}$} such that for any
sufficiently large group {${G}$}, the expected value of the
second largest (in absolute value) eigenvalue of the normalized
adjacency matrix of the Cayley graph with respect to
{${c(\epsilon ) log |G|}$} random elements is less than
{${\epsilon }$}. We reduce the number of elements to
{${c(\epsilon )log D(G)}$} (for the same {${c}$}),
where {${D(G)}$} is the sum of the dimensions of the
irreducible representations of {${G}$}. In sufficiently
non-abelian families of groups (as measured by these dimensions), {${log D(G)}$} is asymptotically {${(1/2)log|G|}$}. As is well known, a small eigenvalue implies large graph expansion (and conversely); see Tanner84 and AlonMilman84-2,AlonMilman84-1. For any specified eigenvalue or expansion, therefore, random Cayley graphs (of sufficiently non-abelian groups) require only half as many edges as was previously known.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2004,
volume = {6},
number = {2},
pages = {523-528},
url = {http://www.dmtcs.org/volumes/abstracts/dm060222.abs.html}
}
@Article{DMTCS-070101,
author = {Arthur Holshouser and Harold Reiter},
title = {Two Pile Move-Size Dynamic Nim},
keywords = {Nim, dynamic, combinatorial games},
abstract = {The purpose of this paper is to solve a special class of combinational games consisting of two-pile counter pickup games for
which the maximum number of counters that can be removed on each
successive move changes during the play of the games. Two players
alternate moving. Each player in his turn first chooses one of the
piles, and his choice of piles can change from move to move. He then
removes counters from this chosen pile. A function
{${f:Z^{+} {\rightarrow} Z^{+} }$}
is given which determines the maximum size of the next move in terms
of the current move size. The game ends as soon as one of the two
piles is empty, and the winner is the last player to move in the
game. The games for which {${f(k)=k, f(k)=2k}$}, and
{${f(k)=3k}$} use the same formula for computing the smallest
winning move size. Here we find all the functions {${f}$} for
which this formula works, and we also give the winning strategy for
each function. See Holshouser, A, James Rudzinski and Harold
Reiter: Dynamic One-Pile Nim for a discussion of the single pile game.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {1-10},
url = {http://www.dmtcs.org/volumes/abstracts/dm070101.abs.html}
}
@Article{DMTCS-070102,
author = {Mohamud Mohammed},
title = {Infinite families of accelerated series for some classical constants by the Markov-WZ Method},
keywords = {WZ theory, series convergence, hypergeometric series},
abstract = {In this article we show the Markov-WZ Method in action as it finds rapidly converging series representations for a
given hypergeometric series. We demonstrate the method by finding
new representations for {${log(2),\zeta (2)}$} and
{${\zeta (3)}$}. },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {11-24},
url = {http://www.dmtcs.org/volumes/abstracts/dm070102.abs.html}
}
@Article{DMTCS-070103,
author = {L. Sunil Chandran and Vadim V. Lozin and C.R. Subramanian},
title = {Graphs of low chordality},
keywords = {induced cycles, chordality},
abstract = {The chordality of a graph with at least one cycle is the length of the longest induced cycle in it. The odd (even) chordality
is defined to be the length of the longest induced odd (even) cycle in
it. Chordal graphs have chordality at most 3. We show that
co-circular-arc graphs and co-circle graphs have even chordality at
most 4. We also identify few other classes of graphs having bounded
(by a constant) chordality values.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {25-36},
url = {http://www.dmtcs.org/volumes/abstracts/dm070103.abs.html}
}
@Article{DMTCS-070104,
author = {David R. Wood},
title = {Acyclic, Star and Oriented Colourings of Graph Subdivisions},
keywords = {graph, graph colouring, star colouring, star chromatic number, acyclic colouring, acyclic chromatic number, oriented colouring, oriented chromatic number, subdivision},
abstract = {Let {${G}$} be a graph with chromatic number {${\chi (G)}$}. A vertex colouring of {${G}$} is
\emph{acyclic} if each bichromatic subgraph is a forest. A
\emph{star colouring} of {${G}$} is an acyclic
colouring in which each bichromatic subgraph is a star forest. Let
{${\chi _{a}(G)}$} and
{${\chi _{s}(G)}$} denote the acyclic and star
chromatic numbers of {${G}$}. This paper investigates acyclic
and star colourings of subdivisions. Let {${G'}$} be the graph
obtained from {${G}$} by subdividing each edge once. We prove
that acyclic (respectively, star) colourings of {${G'}$}
correspond to vertex partitions of {${G}$} in which each
subgraph has small arboricity (chromatic index). It follows that
{${\chi _{a}(G')}$}, {${\chi _{s}(G')}$}
and {${\chi (G)}$} are tied, in the sense that each is bounded
by a function of the other. Moreover the binding functions that we
establish are all tight. The \emph{oriented chromatic
number} {${{\chi }^{{\rightarrow}}(G)}$} of an
(undirected) graph {${G}$} is the maximum, taken over all
orientations {${D}$} of {${G}$}, of the minimum number
of colours in a vertex colouring of {${D}$} such that between
any two colour classes, all edges have the same direction. We prove
that {${{\chi }^{{\rightarrow}}(G')=\chi (G)}$}
whenever {${\chi (G)\ge 9}$}.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {37-50},
url = {http://www.dmtcs.org/volumes/abstracts/dm070104.abs.html}
}
@Article{DMTCS-070105,
author = {Gérard H. E. Duchamp and Hatem Hadj Kacem and Eric Laugerotte},
title = {Algebraic elimination of {${\epsilon }$}-transitions},
keywords = {Automata with multiplicities, epsilon-transitions, behaviour, star of matrices},
abstract = {We here describe a method of removing the {${\epsilon }$}-transitions of a weighted automaton. The
existence of a solution for this removal depends on the existence of
the star of a single matrix which, in turn, is based on the
computation of the stars of scalars in the ground semiring. We discuss
two aspects of the star problem (by infinite sums and by equations)
and give an algorithm to suppress the
{${\epsilon }$}-transitions and preserve the behaviour. Running
complexities are computed. },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {51-70},
url = {http://www.dmtcs.org/volumes/abstracts/dm070105.abs.html}
}
@Article{DMTCS-070106,
author = {M. D. Atkinson},
title = {Some equinumerous pattern-avoiding classes of permutations},
keywords = {Permutations, patterns, enumeration},
abstract = {Suppose that {${p,q,r,s}$} are non-negative integers with {${m=p+q+r+s}$}. The class {${X(p,q,r,s)}$} of permutations that contain no pattern of the form {${\alpha \beta \gamma }$} where {${|\alpha |=r, |\gamma |=s}$} and {${\beta }$} is any arrangement of {${\{1,2,{\ldots},p\}\cup \{m-q+1, m-q+2, {\ldots},m\}}$} is considered. A recurrence relation to enumerate the permutations of {${X(p,q,r,s)}$} is established. The method of proof also shows that {${X(p,q,r,s)=X(p,q,1,0)X(1,0,r,s)}$} in the sense of permutational composition.\par 2000 MATHEMATICS SUBJECT CLASSIFICATION: 05A05},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {71-74},
url = {http://www.dmtcs.org/volumes/abstracts/dm070106.abs.html}
}
@Article{DMTCS-070107,
author = {Chunhui Lai},
title = {An extremal problem on potentially {${K_{p,1,1}}$}-graphic sequences},
keywords = {graph; degree sequence; potentially {${K_{p,1,1}}$}-graphic},
abstract = {A sequence {${S}$} is potentially {${K_{p,1,1}}$} graphical if it has a realization containing a {${K_{p,1,1}}$} as a subgraph, where {${K_{p,1,1}}$} is a complete 3-partite graph with partition sizes
{${p,1,1}$}. Let {${\sigma (K_{p,1,1}, n)}$} denote the smallest degree sum
such that every {${n}$}-term graphical sequence {${S}$} with {${\sigma (S)\ge
\sigma (K_{p,1,1}, n)}$} is potentially {${K_{p,1,1}}$} graphical. In this
paper, we prove that {${\sigma (K_{p,1,1}, n)\ge 2[((p+1)(n-1)+2)/2]}$}
for {${n \ge p+2}$}. We conjecture that equality holds for {${n \ge
2p+4}$}. We prove that this conjecture is true for {${p = 3}$}.
AMS Subject Classifications: 05C07, 05C35},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {75-80},
url = {http://www.dmtcs.org/volumes/abstracts/dm070107.abs.html}
}
@Article{DMTCS-070108,
author = {Shunji Ito and Hiromi Ei},
title = {Tilings from some non-irreducible, Pisot substitutions},
keywords = {Substitution, Pisot number, atomic surface, tiling, fractal, dynamical system},
abstract = {A generating method of self-affine tilings for Pisot, unimodular, irreducible substitutions, as well as the fact that the associated substitution
dynamical systems are isomorphic to rotations on the torus are established in
P. Arnoux and S. Ito.
The aim of this paper is to extend these facts in the
case where the characteristic polynomial of a substitution is non-irreducible
for a special class of substitutions on five letters.
Finally we show that the substitution dynamical systems for this class are
isomorphic to induced transformations of rotations on the torus.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {81-122},
url = {http://www.dmtcs.org/volumes/abstracts/dm070108.abs.html}
}
@Article{DMTCS-070109,
author = {Ana M. Breda and Altino F. Santos},
title = {Dihedral f-tilings of the sphere by rhombi and triangles},
keywords = {dihedral tilings, isometric foldings, spherical trigonometry, WCSQ},
abstract = {We classify, up to an isomorphism, the class of all dihedral f-tilings of {${S^{2}}$}, whose prototiles are a spherical triangle
and a spherical rhombus. The equiangular case was considered and
classified in Ana M. Breda and Altino F. Santos, Dihedral
f-tilings of the sphere by spherical triangles and equiangular
well-centered quadrangles. Here we complete
the classification considering the case of non-equiangular rhombi. },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {123-140},
url = {http://www.dmtcs.org/volumes/abstracts/dm070109.abs.html}
}
@Article{DMTCS-070110,
author = {Abbas, N. and Culberson, J. and Stewart, L.},
title = {Recognizing Maximal Unfrozen Graphs with respect to Independent Sets is CO-NP-complete},
keywords = {graph, independent set, co-NP-complete, extremal, unfrozen},
abstract = {A graph is unfrozen with respect to {${k}$} independent set if it has an independent set of size {${k}$} after the addition of any edge. The problem of recognizing such graphs is known to be NP-complete. A graph is maximal if the addition of one edge means it is no longer unfrozen. We designate the problem of recognizing maximal unfrozen graphs as MAX({${U}$}({${k}$}-SET)) and show that this problem is CO-NP-complete. This partially fills a gap in known complexity cases of maximal NP-complete problems, and raises some interesting open conjectures discussed in the conclusion. },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {141-154},
url = {http://www.dmtcs.org/volumes/abstracts/dm070110.abs.html}
}
@Article{DMTCS-070111,
author = {Vida Dujmovi{\'c} and David R. Wood},
title = {Stacks, Queues and Tracks: Layouts of Graph Subdivisions},
keywords = {graph layout, graph drawing, track layout, stack layout, queue layout, book embedding, track-number, queue-number, stack-number, page-number, book-thickness, 2-track thickness, geometric thickness, subdivision, three-dimensional graph drawing},
abstract = {{A \emph{{${k}$}-stack layout} (respectively, \emph{{${k}$}-queuelayout}) of a graph consists of a total order of the vertices, and a partition of the edges into {${k}$} sets of non-crossing (non-nested) edges with respect to
the vertex ordering. A \emph{{${k}$}-track layout} of a graph consists of a vertex
{${k}$}-colouring, and a total order of each vertex colour class, such that between
each pair of colour classes no two edges cross. The \emph{stack-number}
(respectively, \emph{queue-number}, \emph{track-number}) of a graph {${G}$},
denoted by {${sn(G)}$} ({${qn(G)}$}, {${tn(G)}$}), is the minimum {${k}$} such that {${G}$} has a
{${k}$}-stack ({${k}$}-queue, {${k}$}-track) layout.\par}
{This paper studies stack, queue, and track layouts of graph subdivisions. It
is known that every graph has a {${3}$}-stack subdivision. The best known upper
bound on the number of division vertices per edge in a {${3}$}-stack subdivision of
an {${n}$}-vertex graph {${G}$} is improved from {${O(log n)}$} to
{${O(log min\{sn(G),qn(G)\})}$}. This result reduces the question of whether
queue-number is bounded by stack-number to whether {${3}$}-stack graphs have
bounded queue number.\par}
{
It is proved that every graph has a {${2}$}-queue subdivision, a {${4}$}-track
subdivision, and a mixed {${1}$}-stack {${1}$}-queue subdivision. All these values are
optimal for every non-planar graph. In addition, we characterise those graphs
with {${k}$}-stack, {${k}$}-queue, and {${k}$}-track subdivisions, for all values of {${k}$}.
The number of division vertices per edge in the case of {${2}$}-queue and {${4}$}-track
subdivisions, namely {${O(log qn(G))}$}, is optimal to within a constant factor,
for every graph {${G}$}.
\par}{
Applications to 3D polyline grid drawings are presented. For example, it is
proved that every graph {${G}$} has a 3D polyline grid drawing with the vertices on
a rectangular prism, and with {${O(log qn(G))}$} bends per edge. Finally, we
establish a tight relationship between queue layouts and so-called {${2}$}-track
thickness of bipartite graphs.
\par}},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {155-202},
url = {http://www.dmtcs.org/volumes/abstracts/dm070111.abs.html}
}
@Article{DMTCS-070112,
author = {Hosseini Dolama, Mohammad and Sopena, Eric},
title = {On the maximum average degree and the incidence chromatic number of a graph},
keywords = {incidence coloring, k-degenerated graph, planar graph, maximum average degree},
abstract = {We prove that the incidence chromatic number of every 3-degenerated graph {${G}$} is at most {${\Delta (G)+4}$}. It is known that the incidence
chromatic number of every graph {${G}$} with maximum average
degree {${mad(G)<3}$} is at most {${\Delta
(G)+3}$}. We show that when {${\Delta (G) \ge 5}$}, this bound may be decreased to {${\Delta (G)+2}$}. Moreover, we show
that for every graph {${G}$} with
{${mad(G)<22/9}$} (resp. with {${mad(G)<16/7}$} and {${\Delta (G)\ge 4}$}),
this bound may be decreased to {${\Delta (G)+2}$} (resp. to {${\Delta (G)+1}$}). },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {203-216},
url = {http://www.dmtcs.org/volumes/abstracts/dm070112.abs.html}
}
@Article{DMTCS-070113,
author = {Kumar Neeraj Verma and Jean Goubault-Larrecq},
title = {Karp-Miller Trees for a Branching Extension of VASS},
keywords = {branching vector addition systems, Karp-Miller trees, coverability, multiplicative exponential linear logic, equational tree automata},
abstract = {We study BVASS (Branching VASS) which extend VASS (Vector Addition Systems with States) by allowing addition transitions that merge two configurations. Runs in BVASS are tree-like structures instead of linear
ones as for VASS. We show that the construction of Karp-Miller trees
for VASS can be extended to BVASS. This entails that the coverability
set for BVASS is computable. This allows us to obtain decidability
results for certain classes of equational tree automata with an
associative-commutative symbol. Recent independent work by de Groote et
al. implies that decidability of reachability in BVASS is equivalent
to decidability of provability in MELL (multiplicative exponential
linear logic), which is still an open problem. Hence our results are
also a step towards answering this question in the affirmative.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {217-230},
url = {http://www.dmtcs.org/volumes/abstracts/dm070113.abs.html}
}
@Article{DMTCS-070114,
author = {Stavros D. Nikolopoulos and Leonidas Palios},
title = {On the Recognition of Bipolarizable and {${P_{4}}$}-simplicial Graphs},
keywords = {Bipolarizable (Raspail) graph, {${P_{4}}$}-simplicial graph, perfectly orderable graph, recognition, algorithm, complexity},
abstract = {The classes of Raspail (also known as Bipolarizable) and {${P_{4}}$}-simplicial graphs were introduced by Ho{\`a}ng and Reed who showed that both classes are perfectly
orderable and admit polynomial-time recognition algorithms
HR1. In this paper, we consider the recognition problem on
these classes of graphs and present algorithms that solve it in
{${O(n m)}$} time. In particular, we prove properties and show that we
can produce bipolarizable and {${P_{4}}$}-simplicial orderings on the
vertices of the input graph {${G}$}, if such orderings exist, working
only on {${P_{3}}$}s that participate in a {${P_{4}}$} of {${G}$}. The proposed
recognition algorithms are simple, use simple data structures and
both require {${O(n + m)}$} space. Additionally, we show how our
recognition algorithms can be augmented to provide certificates,
whenever they decide that {${G}$} is not bipolarizable or {${P_{4}}$}-simplicial;
the augmentation takes {${O(n + m)}$} time and space.
Finally, we include a diagram on class inclusions and the
currently best recognition time complexities for a number of
perfectly orderable classes of graphs.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {231-254},
url = {http://www.dmtcs.org/volumes/abstracts/dm070114.abs.html}
}
@Article{DMTCS-070115,
author = {David R. Wood},
title = {Queue Layouts of Graph Products and Powers},
keywords = {graph, queue layout, cartesian product, {${d}$}-dimensional grid graph, {${d}$}-dimensional toroidal grid graph, Hamming graph},
abstract = {A \emph{{${k}$}-queue layout} of a graph {${G}$} consists of a linear order {${\sigma }$} of {${V(G)}$}, and a partition of {${E(G)}$} into {${k}$} sets, each of which contains no two edges that are nested in {${\sigma }$}. This paper studies queue layouts of graph products and powers },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {255-268},
url = {http://www.dmtcs.org/volumes/abstracts/dm070115.abs.html}
}
@Article{DMTCS-070116,
author = {Shigeki Akiyama and Nertila Gjini},
title = {Connectedness of number theoretical tilings},
keywords = {Tile, Connectedness, Pisot number, number system},
abstract = {Let {${T=T(A,D)}$} be a self-affine tile in {${{\reals}^{n}}$}
defined by
an integral expanding matrix {${A}$} and a digit set {${D}$}. In
connection with canonical number systems, we study connectedness
of {${T}$} when {${D}$} corresponds to the set of consecutive integers
{${\{0,1,..., |det(A)|-1\}}$}. It is shown that in {${{\reals}^{3}}$}
and {${{\reals}^{4}}$}, for any integral expanding matrix {${A}$},
{${T(A,D)}$} is connected.
We also study the connectedness of Pisot dual tilings which play
an important role in the study of {${\beta }$}-expansion, substitution
and symbolic dynamical system. It is shown that each tile
generated by a Pisot unit of degree {${3}$} is arcwise connected. This
is naturally expected since the digit set consists of consecutive
integers as above. However surprisingly, we found families of
disconnected Pisot dual tiles of degree {${4}$}. Also we give a simple
necessary and sufficient condition for the connectedness of the
Pisot dual tiles of degree {${4}$}. As a byproduct, a complete
classification of the {${\beta }$}-expansion of {${1}$} for quartic Pisot
units is given.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {269-312},
url = {http://www.dmtcs.org/volumes/abstracts/dm070116.abs.html}
}
@Article{DMTCS-070117,
author = {Charles Knessl and Wojciech Szpankowski},
title = {Enumeration of Binary Trees and Universal Types},
keywords = {Binary trees, types, Lempel-Ziv'78, path length},
abstract = {Binary unlabeled ordered trees (further called binary trees) were studied at least since Euler, who enumerated them.
The number of such trees with {${n}$} nodes is now known as the Catalan number.
Over the years various interesting questions about the statistics
of such trees were investigated (e.g., height and path length
distributions for a randomly selected tree). Binary
trees find an abundance of applications in computer science.
However, recently Seroussi posed a new and interesting problem motivated by
information theory considerations:
how many binary trees of a \emph{given path length} (sum of depths) are there?
This question arose in the study of \emph{universal types} of sequences.
Two sequences of length {${p}$} have the same universal type
if they generate the same set of phrases in the incremental parsing
of the Lempel-Ziv'78 scheme since one proves that such sequences
converge to the same empirical distribution.
It turns out that the number of distinct types of sequences of length {${p}$}
corresponds to the number of binary (unlabeled and ordered) trees, {${T_{p}}$},
of given path length {${p}$} (and also the number of distinct
Lempel-Ziv'78 parsings of length {${p}$} sequences).
We first show that the number of binary trees with given path length
{${p}$} is asymptotically equal to
{${T_{p} ~ 2^{2p/(log_{2} p)(1+O(log ^{-2/3} p))}}$}. Then
we establish various limiting distributions for the number of nodes
(number of phrases in the Lempel-Ziv'78 scheme)
when a tree is selected randomly among all trees of given
path length {${p}$}.
Throughout, we use methods of analytic algorithmics such as
generating functions and complex asymptotics, as well as
methods of applied mathematics such as the WKB method and matched
asymptotics.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {7},
number = {1},
pages = {313-400},
url = {http://www.dmtcs.org/volumes/abstracts/dm070117.abs.html}
}
@Article{DMTCS-080101,
author = {Angelelli, Enrico and Speranza, Maria Grazia, and Tuza, Tsolt},
title = {New bounds and algorithms for on-line scheduling: two identical processors, known sum and upper bound on the tasks},
keywords = {semi on-line scheduling, parallel processors, competitive analysis},
abstract = {In this paper we study a semi on-line version of the classical multiprocessor scheduling problem on two identical processors. We assume that the sum of the tasks and an upper bound gamma on the size of each task are known. Each task has to be assigned upon arrival and the assignment cannot be changed later. The objective is the minimization of the maximum completion time on the processors. In this paper we propose new algorithms and improve known lower and upper bounds on the competitive ratio. Algorithms and bounds depend on the value of gamma. An optimal algorithm is obtained for gamma in the interval [ 1/n,2(n+1)/n(2n+1) ] and gamma = (2n-1)/2n(n-1), where n is any integer value larger or equal 2.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2006,
volume = {8},
number = {1},
pages = {1-16},
url = {http://www.dmtcs.org/volumes/abstracts/dm080101.abs.html}
}
@Article{DMTCS-080102,
author = {R. Balasubramanian and C.R. Subramanian},
title = {On Sampling Colorings of Bipartite Graphs},
keywords = {Graph colorings, Markov chains, Analysis of algorithms},
abstract = {We study the problem of efficiently sampling {${k}$}-colorings of bipartite graphs. We show that a class of markov chains cannot be used as efficient
samplers. Precisely,
we show that, for any {${k}$}, {${6 \le k \le n^{\{1/3-\epsilon \}}}$}, {${\epsilon > 0}$}
fixed, \emph{almost every} bipartite graph on {${n+n}$} vertices is such
that the mixing time of any markov chain asymptotically uniform on its
{${k}$}-colorings is exponential
in {${n/k^{2}}$} (if it is allowed to only change the colors of {${O(n/k)}$} vertices
in a single transition step). This kind of exponential time mixing is
called \emph{torpid mixing}.
As a corollary, we show that there are (for every {${n}$}) bipartite graphs on
{${2n}$} vertices with {${\Delta (G) = \Omega (\ln n)}$} such that for every
{${k}$}, {${6 \le k \le \Delta /(6 \ln \Delta )}$},
each member of a large class of chains mixes torpidly.
While, for fixed {${k}$}, such negative results are implied by
the work of CDF, our results are more general in that they
allow {${k}$} to grow with {${n}$}.
We also show that these negative results hold true for {${H}$}-colorings
of bipartite graphs provided {${H}$} contains a spanning complete bipartite
subgraph. We also present explicit examples of colorings ({${k}$}-colorings
or {${H}$}-colorings) which admit 1-cautious chains that are
ergodic and are shown to have exponential mixing time.
While, for fixed {${k}$} or fixed {${H}$}, such negative results are implied by
the work of CDF, our results are more general in that they
allow {${k}$} or {${H}$} to vary with {${n}$}. },
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2006,
volume = {8},
number = {1},
pages = {17-30},
url = {http://www.dmtcs.org/volumes/abstracts/dm080102.abs.html}
}
@Article{DMTCS-080104,
author = {M. Kouider and P.D. Vestergaard},
title = {Generalized connected domination in graphs},
keywords = {connected domination, domination, tree},
abstract = {As a generalization of connected domination in a graph {${G}$} we consider domination by sets having at most {${k}$} components. The order {${\gamma _{c}^{k} (G)}$} of such a smallest set we relate to {${\gamma _{c}(G)}$}, the order
of a smallest connected dominating set.
For a tree {${T}$} we give bounds on {${\gamma _{c}^{k} (T)}$} in terms of
minimum valency and diameter.
For trees the inequality {${\gamma _{c}^{k} (T)\le n-k-1}$} is known to
hold, we determine the class of trees, for which equality holds.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2006,
volume = {8},
number = {1},
pages = {57-64},
url = {http://www.dmtcs.org/volumes/abstracts/dm080104.abs.html}
}
@Article{DMTCS-080105,
author = {Stavros D. Nikolopoulos and Leonidas Palios},
title = {Recognizing HH-free, HHD-free, and Welsh-Powell Opposition Graphs},
keywords = {HH-free graph, HHD-free graph, Welsh-Powell opposition graph, perfectly orderable graph, recognition.},
abstract = {In this paper, we consider the recognition problem on three classes of perfectly orderable graphs, namely, the HH-free, the HHD-free, and the Welsh-Powell opposition graphs (or WPO-graphs). In particular, we prove properties of the chordal completion of a graph and show that a modified version of the classic linear-time algorithm for testing for a perfect elimination ordering can be efficiently used to determine in {${O(n }$}min \{{${m \alpha (n,n), m + n^{2} }$}log {${n}$}\}) time whether
a given graph {${G}$} on {${n}$} vertices and {${m}$} edges contains a house or a hole; this implies an {${O(n }$}min \{{${m \alpha (n,n), m + n^{2} }$}log {${n}$}\})-time and {${O(n+m)}$}-space algorithm for recognizing HH-free graphs, and in turn leads to an HHD-free graph recognition algorithm exhibiting the same time and space complexity. We also show that determining whether the complement {${\overline{G}}$} of the graph {${G}$} is HH-free can be efficiently resolved in {${O(n m)}$} time using {${O(n^{2})}$} space, which leads to an {${O(n m)}$}-time and {${O(n^{2})}$}-space algorithm for recognizing WPO-graphs. The previously best algorithms for recognizing HH-free, HHD-free, and WPO-graphs required {${O(n^{3})}$} time and {${O(n^{2})}$} space.},
journal = {Discrete Mathematics and Theoretical Computer Science},
year = 2006,
volume = {8},
number = {1},
pages = {65-82},
url = {http://www.dmtcs.org/volumes/abstracts/dm080105.abs.html}
}
@inproceedings{DMTCS-AA0101,
author = {Nicolas Destainville},
title = {Mixing Times of Plane Random Rhombus Tilings},
keywords = {Random tilings, Discrete dynamical systems, Markovian processes, Quasicrystals},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {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 chains. We determine the convergence
rates of these dynamical processes towards the statistical equilibrium
distributions and we demonstrate that the dynamics are rapidly mixing: the
ergodic times are polynomial in the number of tiles up to logarithmic
corrections. We use an inherent symmetry of tiling sets which enables to
decompose them into smaller subsets where a technique from probability theory,
the so-called coupling technique, can be applied. We also point out an
interesting occurrence in this work of extreme-value statistics, namely Gumbel
distributions.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {1-22},
url = {http://www.dmtcs.org/proceedings/html/dmAA0101.abs.html}
}
@inproceedings{DMTCS-AA0102,
author = {Joakim Linde and Cristopher Moore and Mats G. Nordahl},
title = {An n-Dimensional Generalization of the Rhombus Tiling},
keywords = {Tilings, Discrete Dynamical Systems, Quasicrystals},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {Several classic tilings, including rhombuses and dominoes, possess height functions which allow us to 1) prove ergodicity and polynomial
mixing times for Markov chains based on local moves, 2) use coupling
from the past to sample perfectly random tilings, 3) map the
statistics of random tilings at large scales to physical models of
random surfaces, and and 4) are related to the ``arctic circle''
phenomenon. However, few examples are known for which this approach
works in three or more dimensions. Here we show that the rhombus
tiling can be generalized to {${n}$}-dimensional tiles
for any {${n \ge 3}$}.
For each {${n}$}, we show that a certain local move is ergodic, and
conjecture that it has a mixing time of {${O(L^{(n+2)} log L)}$} on
regions of size {${L}$}.
For {${n=3}$}, the tiles are rhombohedra, and the
local move consists of switching between two tilings of a rhombic
dodecahedron. We use coupling from the past to sample random tilings
of a large rhombic dodecahedron, and show that arctic regions exist in
which the tiling is frozen into a fixed state. However, unlike the
two-dimensional case in which the arctic region is an inscribed
circle, here it seems to be octahedral. In addition, height
fluctuations between the boundary of the region and the center appear
to be constant rather than growing logarithmically. We conjecture
that this is because the physics of the model is in a ``smooth'' phase
where it is rigid at large scales, rather than a ``rough'' phase in
which it is elastic.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {23-42},
url = {http://www.dmtcs.org/proceedings/html/dmAA0102.abs.html}
}
@inproceedings{DMTCS-AA0103,
author = {James Propp},
title = {The Many Faces of Alternating-Sign Matrices},
keywords = {Alternating-Sign Matrices, Tilings},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {I give a survey of different combinatorial forms of alternating-sign matrices, starting with the original form introduced
by Mills, Robbins and Rumsey as well as corner-sum matrices,
height-function matrices, three-colorings, monotone triangles,
tetrahedral order ideals, square ice, gasket-and-basket tilings
and full packings of loops.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {43-58},
url = {http://www.dmtcs.org/proceedings/html/dmAA0103.abs.html}
}
@inproceedings{DMTCS-AA0104,
author = {Pierre Arnoux and Val{\'e}rie Berth{\'e} and Hiromi Ei and Shunji Ito},
title = {Tilings, Quasicrystals, Discrete Planes, Generalized Substitutions, and Multidimensional Continued Fractions},
keywords = {Substitutions, translations on compact groups, tilings, atomic surface, fractal sets, Markov partitions, numeration systems},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {The aim of this paper is to give an overview of recent results about tilings, discrete approximations of lines and planes, and Markov partitions
for toral automorphisms. The main tool is a generalization of the notion of
substitution. The simplest examples which correspond to algebraic parameters,
are related to the iteration of one substitution, but we show that it is
possible to treat arbitrary irrational examples by using multidimensional
continued fractions. We give some non-trivial applications to Diophantine
approximation, numeration systems and tilings, and we expose the main unsolved
questions.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {59-78},
url = {http://www.dmtcs.org/proceedings/html/dmAA0104.abs.html}
}
@inproceedings{DMTCS-AA0105,
author = {Andr{\'e} Barb{\'e} and Fritz von Haeseler},
title = {Periodic Patterns in Orbits of Certain Linear Cellular Automata},
keywords = {cellular automata, p-fold bifurcation of periods, finite fields},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {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 field, a universal behavior for the evolution of
periodic verticals.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {79-94},
url = {http://www.dmtcs.org/proceedings/html/dmAA0105.abs.html}
}
@inproceedings{DMTCS-AA0106,
author = {Barrett, Christopher L. and Hunt, Harry B., III and Marathe, Madhav V. and Ravi, S. S. and Rosenkrantz, Daniel J. and
Stearns, Richard E. and Tosic, Predrag T.},
title = {Gardens of Eden and Fixed Points in Sequential Dynamical Systems},
keywords = {Discrete Dynamical Systems, Cellular Automata, Computational Complexity},
editor = {Cori, Robert and Mazoyer, Jacques and Morvan, Michel and Mosseri, R{\'e}my},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {A class of finite discrete dynamical systems, called \textbf{Sequential Dynamical Systems} (SDSs), was proposed in
[BMR99,BR99] as an abstract model of computer simulations.
Here, we address some questions concerning two special types
of the SDS configurations, namely Garden of Eden and
Fixed Point configurations.
A configuration C of an SDS is a Garden of Eden
(GE) configuration if it cannot be reached from any configuration.
A necessary and sufficient condition for the non-existence of GE
configurations in SDSs whose state values are from a finite
domain was provided in [MR00].
We show this condition is sufficient but not necessary
for SDSs whose state values are drawn from an infinite domain.
We also present results that relate the existence of GE configurations
to other properties of an SDS.
A configuration C of an SDS is a fixed point
if the transition out of C is to C itself.
The FIXED POINT EXISTENCE (or FPE) problem is to determine whether a given SDS
has a fixed point.
We show that the FPE problem is \textbf{NP}-complete even for some
simple classes of SDSs (e.g., SDSs in which each local transition
function is from the set \{NAND, XNOR\}).
We also identify several classes of SDSs (e.g.,
SDSs with linear or monotone local transition functions)
for which the FPE problem can be solved efficiently.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {95-110},
url = {http://www.dmtcs.org/proceedings/html/dmAA0106.abs.html}
}
@inproceedings{DMTCS-AA0107,
author = {Sergei Bespamyatnikh},
title = {Enumerating Triangulations of Convex Polytopes},
keywords = {polytope, bistellar flip, triangulation, enumeration},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {A triangulation of a finite point set {${A}$} in {${R^{d}}$} is
a geometric simplicial complex which covers the convex hull of {${A}$}
and whose vertices are points of {${A}$}.
We study the graph of triangulations whose vertices represent the
triangulations and whose edges represent geometric bistellar flips.
The main result of this paper is that the graph of triangulations
in three dimensions is connected when the points of {${A}$} are in convex
position.
We introduce a tree of triangulations and
present an algorithm for enumerating triangulations
in {${O(log log n)}$} time per triangulation.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {111-122},
url = {http://www.dmtcs.org/proceedings/html/dmAA0107.abs.html}
}
@inproceedings{DMTCS-AA0108,
author = {Fran\c{c}ois Boulier and Florent Hivert and Daniel Krob and Jean-Christophe Novelli},
title = {Pseudo-Permutations {I}{I}: Geometry and Representation Theory},
keywords = {Hyperplane Arrangements, Symmetric Group, Permutations, q-analogs},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {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 the module of the
pseudo-permutations over the symmetric group and provide the characteristics
of this action.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {123-132},
url = {http://www.dmtcs.org/proceedings/html/dmAA0108.abs.html}
}
@inproceedings{DMTCS-AA0109,
author = {Del Lungo, Alberto and Mirolli, Massimo and Pinzani, Renzo and Rinaldi, Simone},
title = {A Bijection for Directed-Convex Polyominoes},
keywords = {cycle lemma, directed-convex polyominoes, binomial coefficients, lattice paths},
editor = {Cori, Robert and Mazoyer, Jacques and Morvan, Michel and Mosseri, R{\'e}my},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {In this paper we consider two classes of lattice paths on the plane which use \textit{north},
\textit{east},
\textit{south}, and
\textit{west} unitary
steps, beginning and ending at {${(0,0)}$}. We enumerate them according to
the number of steps by means of bijective arguments; in particular, we apply
the cycle lemma. Then, using these results, we provide a bijective proof for
the number of directed-convex polyominoes having a fixed number of rows and
columns.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {133-144},
url = {http://www.dmtcs.org/proceedings/html/dmAA0109.abs.html}
}
@inproceedings{DMTCS-AA0110,
author = {J{\'e}r{\^o}me Durand-Lose},
title = {Representing Reversible Cellular Automata with Reversible Block Cellular Automata},
keywords = {Cellular automata, reversibility, block cellular automata, partitioning cellular automata},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {Cellular automata are mappings over infinite lattices such that each cell is updated according to the states around it and a unique local
function. Block permutations are mappings that generalize a given permutation
of blocks (finite arrays of fixed size) to a given partition of the lattice in
blocks. We prove that any d-dimensional reversible cellular automaton
can be exp ressed as the composition of d+1 block permutations. We built a
simulation in linear time of reversible cellular automata by reversible block
cellular automata (also known as partitioning CA and CA with the Margolus
neighborhood) which is valid for both finite and infinite configurations.
This proves a 1990 conjecture by Toffoli and Margolus \textit{Physica D} 45
improved by Kari in 1996 \textit{Mathematical System Theory} 29).},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {145-154},
url = {http://www.dmtcs.org/proceedings/html/dmAA0110.abs.html}
}
@inproceedings{DMTCS-AA0111,
author = {M. Reza Emamy-Khansary and Martin Ziegler},
title = {New Bounds for Hypercube Slicing Numbers},
keywords = {Hypercube cut number, linear separability, combinatorial geometry},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {What is the maximum number of edges of the {${d}$}-dimensional hypercube, denoted by {${S(d,k)}$}, that can be sliced by
{${k}$}
hyperplanes?
This question on combinatorial properties of Euclidean geometry arising from
linear separability considerations in the theory of Perceptrons has become an
issue on its own. We use computational and combinatorial methods to obtain new
bounds for {${S(d,k)}$},
{${d \le 8}$}. These strengthen earlier
results on hypercube cut numbers.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {155-164},
url = {http://www.dmtcs.org/proceedings/html/dmAA0111.abs.html}
}
@inproceedings{DMTCS-AA0112,
author = {Robert Erra and Nik Lygeros and Nigel Stewart},
title = {On Minimal Strings Containing the Elements of {${S_{n}}$} by Decimation},
keywords = {Hyperplane Arrangements, Symmetric Group, Permutations, {${q}$}-analogs},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {The \emph{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 that sequences of this form are
{${O(n^{2})}$} in length, but finding optimal solutions can be
difficult.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {165-176},
url = {http://www.dmtcs.org/proceedings/html/dmAA0112.abs.html}
}
@inproceedings{DMTCS-AA0113,
author = {Kellie M. Evans},
title = {Larger than Life: Digital Creatures in a Family of Two-Dimensional Cellular Automata},
keywords = {Cellular automata, spaceships, Game of Life, Larger than Life},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {We introduce the Larger than Life family of two-dimensional two-state
cellular automata that generalize certain nearest neighbor outer
totalistic cellular automaton rules to large neighborhoods. We
describe linear and quadratic rescalings of John Conway's celebrated
Game of Life to these large neighborhood cellular automaton rules and
present corresponding generalizations of Life's famous gliders and
spaceships. We show that, as is becoming well known for nearest
neighbor cellular automaton rules, these ``digital creatures'' are
ubiquitous for certain parameter values.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {177-192},
url = {http://www.dmtcs.org/proceedings/html/dmAA0113.abs.html}
}
@inproceedings{DMTCS-AA0114,
author = {Travis Herbranson and Don Rawlings},
title = {A Sequential Search Distribution: Proofreading, Russian Roulette, and the Incomplete {${q}$}-Eulerian Polynomials},
keywords = {California Polytechnic State University, San Luis Obispo, California 93407},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {The distribution for the number of searches needed to find {${k}$} of {${n}$} lost objects is expressed in terms of a
refinement of the {${q}$}-Eulerian polynomials, for which formulae are
developed involving homogeneous symmetric polynomials. In the case when
{${k=n}$} and the find probability remains constant, relatively simple and
efficient formulas are obtained. From our main theorem, we further (1) deduce
the inverse absorption distribution and (2) determine the expected number of
times the survivor pulls the trigger in an {${n}$}-player game of Russian
roulette.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {193-202},
url = {http://www.dmtcs.org/proceedings/html/dmAA0114.abs.html}
}
@inproceedings{DMTCS-AA0115,
author = {Daniel Krob and Ekaterina A. Vassilieva},
title = {Performance Evaluation of Demodulation Methods: a Combinatorial Approach},
keywords = {Young Tableaux, Bijective Combinatorics, Algebraic Combinatorics, Signal Modulation, Signal Processing, Mobile Communications},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = { This paper provides a combinatorial approach for analyzing the
performance of demodulation methods used in GSM. We also show
how to obtain combinatorially a nice specialization of an important
performance evaluation formula, using its connection with a classical
bijection of Knuth between pairs of Young tableaux and
{${\{0,1\}}$}-matrices. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {203-214},
url = {http://www.dmtcs.org/proceedings/html/dmAA0115.abs.html}
}
@inproceedings{DMTCS-AA0116,
author = {Matthieu Latapy},
title = {Partitions of an Integer into Powers},
keywords = {Integer partition, Composition, Lattice, Distributive Lattice, Discrete Dynamical Models, Chip Firing Game},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {In this paper, we use a simple discrete dynamical model to study partitions of integers into powers of another integer.
We extend and generalize some known results about their enumeration
and counting, and we give new structural results.
In particular, we show that the set of these partitions can be ordered
in a natural way which gives the distributive lattice structure to this set.
We also give a tree structure which allow efficient and simple
enumeration of the partitions of an integer.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {215-228},
url = {http://www.dmtcs.org/proceedings/html/dmAA0116.abs.html}
}
@inproceedings{DMTCS-AA0117,
author = {Cl{\'e}mence Magnien and Ha Duong Phan and Laurent Vuillon},
title = {Characterization of Lattices Induced by (extended) Chip Firing Games},
keywords = {Chip Firing Game, Lattice, Discrete Dynamical Model, Sand Pile Model},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {The Chip Firing Game (CFG) is a discrete dynamical model used in physics, computer science and economics.
It is known that the set of configurations reachable from an initial
configuration (this set is called the \textit{configuration space}) can be
ordered as a lattice.
We first present a structural result about this model, which allows us to
introduce some useful tools for describing those lattices.
Then we establish that the class of lattices that are the configuration space
of a CFG is strictly between the class of distributive lattices and the class
of upper locally distributive (or ULD) lattices.
Finally we propose an extension of the model, the \textit{coloured} Chip Firing
Game, which generates exactly the class of ULD lattices.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {229-244},
url = {http://www.dmtcs.org/proceedings/html/dmAA0117.abs.html}
}
@inproceedings{DMTCS-AA0118,
author = {Criel Merino},
title = {The Chip Firing Game and Matroid Complexes},
keywords = {Chip-firing game, Tutte polynomial, Simplicial complex},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {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 proves a conjecture of Richard Stanley
[Sta96] in the particular case of cographic matroids. We also prove
that the multicomplexes constructed are {${M}$}--shellable, so proving a
conjecture of Manoj Chari [Cha97] again in the case of cographic matroids. The
proofs use results on a game for graphs called the chip firing game.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {245-256},
url = {http://www.dmtcs.org/proceedings/html/dmAA0118.abs.html}
}
@inproceedings{DMTCS-AA0119,
author = {Aaron Meyerowitz},
title = {Tiling the Line with Triples},
keywords = {Tiling, one dimension, direct proof},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {It is known the one dimensional prototile {${\{0,a,a+b\}}$} and its reflection {${\{0,b,a+b\}}$} always tile some interval. The subject
has not received a great deal of further attention, although many interesting
questions exist. All the information about tilings can be encoded in a finite
digraph {${D_{ab}}$}. We present several results about cycles and other
structures in this graph. A number of conjectures and open problems are given.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {257-274},
url = {http://www.dmtcs.org/proceedings/html/dmAA0119.abs.html}
}
@inproceedings{DMTCS-AA0120,
author = {Jean-Christophe Novelli and Dominique Rossin},
title = {On the Toppling of a Sand Pile},
keywords = {Sand Pile Model, Young Tableaux},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {In this paper, we provide the first study of the sand pile model {${SPM(0)}$} where we assume that all the grains are numbered with a distinct
integer. We obtain a lower bound on the number of terminal sand piles by
establishing a bijection between a subset of these sand piles and the set of
shifted Young tableaux.
We then prove that this number is at least factorial.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {275-286},
url = {http://www.dmtcs.org/proceedings/html/dmAA0120.abs.html}
}
@inproceedings{DMTCS-AA0121,
author = {Gilles Radenne},
title = {Tilings of a Domain on a Hexagon Mesh with Balanced 3-Tiles},
keywords = {Hexagon, Tiling, Balancing, Matching},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {In this article, we study the question of tilings on a hexagon mesh with balanced 3-tiles. This problem has been studied by Conway and
Lagarias in [CL90], by studying the tiling groups, in fact a
group containing the tiling-groups, and their Cayley graphs. We will use
two different approaches. The first one is based on matchings in bipartite
graphs, which in this case are in correspondance with tilings of domains
by lozenges, and thus can be efficiently studied, using Thurston's
algorithm (see [Thu90]). The second one is based on a color and
balancing approach of Thurston's algorithm, exposed in [Fou96].},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {287-300},
url = {http://www.dmtcs.org/proceedings/html/dmAA0121.abs.html}
}
@inproceedings{DMTCS-AA0122,
author = {Jan Snellman},
title = {A Poset Classifying Non-Commutative Term Orders},
keywords = {free associative algebra, term orders},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {We study a poset N on the free monoid (X*) on a countable alphabet X. This poset is determined by the fact that its total
extensions are precisely the standard term orders on X*. We also
investigate the poset classifying degree-compatible standard term orders, and
the poset classifying sorted term orders. For the latter poset, we give a
Galois coconnection with the Young lattice.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {301-314},
url = {http://www.dmtcs.org/proceedings/html/dmAA0122.abs.html}
}
@inproceedings{DMTCS-AA0123,
author = {Nicolas M. Thi{\'e}ry},
title = {Computing Minimal Generating Sets of Invariant Rings of Permutation Groups with {S}{A}{G}{B}{I}-{G}r{\"o}bner Basis},
keywords = {Invariant Theory, Permutation Group, Discrete Mathematics, Minimal Generating Set, Hironaka Decomposition, SAGBI-Gr{\"o}bner basis,
permuvar, mupad},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {We present a characteristic-free algorithm for computing minimal generating sets of invariant rings of permutation groups. We circumvent the
main weaknesses of the usual approaches (using classical Gröbner basis inside
the full polynomial ring, or pure linear algebra inside the invariant ring) by
relying on the theory of SAGBI-Gr{\"o}bner basis. This theory takes, in this
special case, a strongly combinatorial flavor, which makes it particularly
effective.
Our algorithm does not require the computation of a Hironaka decomposition,
nor even the computation of a system of parameters, and could be parallelized.
Our implementation, as part of the library permuvar for mupad, is in many
cases much more efficient than the other existing software.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {315-328},
url = {http://www.dmtcs.org/proceedings/html/dmAA0123.abs.html}
}
@inproceedings{DMTCS-AA0124,
author = {Alexander Zvonkin},
title = {Megamaps: Construction and Examples},
keywords = {Riemann surface; ramified covering; dessins d'enfants; Belyi function; braid group; Hurwitz scheme},
editor = {Robert Cori and Jacques Mazoyer and Michel Morvan and R{\'e}my Mosseri},
booktitle = {Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001},
abstract = {We consider the usual model of hypermaps or, equivalently, bipartite maps, represented by pairs of permutations that act transitively on a set of
edges {${E}$}. The specific feature of our construction is the fact that the
elements of {${E}$} are themselves (or are labelled by) rather complicated
combinatorial objects, namely, the 4-constellations, while the permutations
defining the hypermap originate from an action of the Hurwitz braid group on
these 4-constellations. The motivation for the whole construction is the
combinatorial representation of the parameter space of the ramified coverings
of the Riemann sphere having four ramification points.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2001,
volume = {AA},
pages = {329-340},
url = {http://www.dmtcs.org/proceedings/html/dmAA0124.abs.html}
}
@inproceedings{DMTCS-AB0101,
author = {Malte Schmick and Mario Markus},
title = {Evidence for intermittency in a granular medium: experiments and simulations.},
keywords = {granular media, intermittency, self-organization},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {We present the first experimental demonstration of intermittency in a granular medium. The medium consists of magnets embedded within spheres. These spheres
are placed in a horizontal Petri dish where they roll by virtue of an alternating, homogenous magnetic field. Due to collisions with the wall, clustering leads to self-organization into ring pieces circulating along the wall. The intermi
ttent behaviour consists of an aperiodical alternation of this circular motion
with a gaslike state extended over the entire dish. Molecular dynamic simulations agree with observations},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {1-10},
url = {http://www.dmtcs.org/proceedings/html/dmAB0101.abs.html}
}
@inproceedings{DMTCS-AB0102,
author = {Cosma Rohilla Shalizi},
title = {Optimal Nonlinear Prediction of Random Fields on Networks},
keywords = {Networks, random fields, sufficient statistics, nonlinear prediction, information theory, recursive estimation},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {It is increasingly common to encounter time-varying random fields on networks (metabolic networks, sensor arrays, distributed computing, etc.). This paper
considers the problem of optimal, nonlinear prediction of these fields, showing
from an information-theoretic perspective that it is formally identical to the
problem of finding minimal local sufficient statistics. I derive general
properties of these statistics, show that they can be composed into global
predictors, and explore their recursive estimation properties. For the special
case of discrete-valued fields, I describe a convergent algorithm to identify
the local predictors from empirical data, with minimal prior information about
the field, and no distributional assumptions.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {11-30},
url = {http://www.dmtcs.org/proceedings/html/dmAB0102.abs.html}
}
@inproceedings{DMTCS-AB0103,
author = {Martin Nilsson and Steen Rasmussen},
title = {Cellular Automata for Simulating Molecular Self-Assembly},
keywords = {Cellular Automata, Lattice Gas, Molecular Self-Assembly, Statistical Mechanics, Thermodynamics},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {We present a lattice gas technique for simulating molecular self-assembly of amphiphilic polymers in aqueous environments.
Water molecules, hydrocarbons tail-groups and amphiphilic head-groups are
explicitly represented on a three dimensional discrete lattice.
Molecules move on the lattice proportional to their continuous momentum. Collision
rules preserve momentum and kinetic energy. Potential energy from
molecular interactions are also included explicitly. Non-trivial thermodynamics
of large scale and long time dynamics are studied. In this paper we specifically demonstrate how, from a random initial
distribution, micelles are formed, and grow until they destabilize and divide.
Eventually a steady state of growing and dividing micelles is formed.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {31-42},
url = {http://www.dmtcs.org/proceedings/html/dmAB0103.abs.html}
}
@inproceedings{DMTCS-AB0104,
author = {Phan Ti and Ha Duong and Thierry, {\'E}ric},
title = {Dynamics of the Picking transformation on integer partitions},
keywords = {discrete dynamical system, integer partitions},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {This paper studies a conservative transformation defined on families of finite sets. It consists in removing one element from each set and adding
a new set composed of the removed elements. This transformation is
conservative in the sense that the union of all sets of the family always
remains the same. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {43-56},
url = {http://www.dmtcs.org/proceedings/html/dmAB0104.abs.html}
}
@inproceedings{DMTCS-AB0105,
author = {Anah\'{\i} Gajardo},
title = {A symbolic projection of Langton's Ant},
keywords = {Symbolic Dynamics, Lorentz Lattice Gas, Cayley Graphs},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {The Langton's ant is studied from the point of view of topological dynamical systems. A new approach which associate a
subshift to the system is proposed. The transition rule is
generalized to the family of bi-regular graphs
{${\Gamma (k,d)}$} and the dependence of the dynamical system
on {${k}$} and {${d}$} is analyzed. A classification of
the {${\Gamma (k,d)}$} graphs based on the dynamical properties
of the subshift is established. Also a hierarchy is defined on the
graphs through the subset relation of the respective subshifts. The
analysis are worked out by establishing an algebraic characterization
of the forbidden words of the subshift.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {57-68},
url = {http://www.dmtcs.org/proceedings/html/dmAB0105.abs.html}
}
@inproceedings{DMTCS-AB0106,
author = {Barrett, Christopher L. and Hunt, Harry B., III and Marathe, Madhav V. and Ravi, S. S. and Rosenkrantz, Daniel J. and Stearns, Richard E.},
title = {Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.},
keywords = {Discrete Dynamical Systems, Cellular Automata, Predecessor Existence, Permutation Existence,
Computational Complexity},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {A class of finite discrete dynamical systems, called Sequential Dynamical Systems (SDSs),
was introduced in [BR99] as a formal model
for analyzing simulation systems.
Here, we address the complexity of two basic problems and
their generalizations for SDSs.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {69-80},
url = {http://www.dmtcs.org/proceedings/html/dmAB0106.abs.html}
}
@inproceedings{DMTCS-AB0107,
author = {Olivier Bodini},
title = {Tiling a Rectangle with Polyominoes},
keywords = {Tiling, Polyomino},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {A polycube in dimension d is a finite union of unit {${d}$}-cubes whose vertices are on knots of the lattice {${Z^{d}}$}. We show that, for each
family of polycubes {${E}$}, there exists a finite set {${F}$} of bricks
(parallelepiped rectangles) such that the bricks which can be
tiled by {${E}$} are exactly the bricks which can be tiled by {${F}$}.
Consequently, if we know the set {${F}$}, then we have an algorithm to
decide in polynomial time if a brick is tilable or not by the tiles of {${E}$}.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {81-88},
url = {http://www.dmtcs.org/proceedings/html/dmAB0107.abs.html}
}
@inproceedings{DMTCS-AB0108,
author = {Arnaud Dartois and Cl{\'e}mence Magnien},
title = { Results and conjectures on the Sandpile Identity on a lattice},
keywords = {Abelian sandpile, Identity, Burning algorithm, Infinite lattice, Toppling},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {In this paper we study the identity of the Abelian Sandpile Model on a rectangular lattice. This configuration can be computed with the
burning algorithm, which, starting from the empty lattice, computes a
sequence of configurations, the last of which is the identity. We
extend this algorithm to an infinite lattice, which allows us to prove
that the first steps of the algorithm on a finite lattice are the same
whatever its size. Finally we introduce a new configuration, which
shares the intriguing properties of the identity, but is easier to
study.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {89-102},
url = {http://www.dmtcs.org/proceedings/html/dmAB0108.abs.html}
}
@inproceedings{DMTCS-AB0109,
author = {Del Lungo, A. and E. Duchi and A. Frosini and S. Rinaldi},
title = {Enumeration of convex polyominoes using the ECO method},
keywords = {convex polyominoes, ECO method, succession rules, kernel method, generating functions.},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {ECO is a method for the enumeration of classes of combinatorial objects based on recursive constructions of such classes. In the
first part of this paper we present a construction for the class
of convex polyominoes based on the ECO method. Then we translate
this construction into a succession rule. The final goal of the
paper is to determine the generating function of convex
polyominoes according to the semi-perimeter, and it is achieved by
applying an idea introduced in [11].},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {103-116},
url = {http://www.dmtcs.org/proceedings/html/dmAB0109.abs.html}
}
@inproceedings{DMTCS-AB0110,
author = {Bruno Durand and Enrico Formenti and Georges Varouchas},
title = {On undecidability of equicontinuity classification for cellular automata},
keywords = {cellular automata, classification, discrete dynamical systems, undecidability},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {Equicontinuity classification is a popular classification of cellular automata based on their dynamical behavior.
In this paper we prove that most of its classes are undecidable.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {117-128},
url = {http://www.dmtcs.org/proceedings/html/dmAB0110.abs.html}
}
@inproceedings{DMTCS-AB0111,
author = {Bruno Durand and Enrico Formenti and Aristide Grange and Zsuzsanna R{\'o}ka},
title = {Number conserving cellular automata: new results on decidability and dynamics},
keywords = {cellular automata, decidability, discrete dynamical systems, classification},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {This paper is a survey on our recent results about number conserving cellular automata. First, we prove the linear time decidability of the property
of number conservation. The sequel focuses on dynamical evolutions
of number conserving cellular automata.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {129-140},
url = {http://www.dmtcs.org/proceedings/html/dmAB0111.abs.html}
}
@inproceedings{DMTCS-AB0112,
author = {Lafaye de Micheaux, N. and Lopez, G. and Vitiello, P. and Beauvois, J. L.},
title = {Formalizing the transformations of a cognitive universe},
keywords = {rewriting, graphs of beliefs, consistency},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {In an effort to continue the pioneering work of Harary in
USA and Flament in France, we have undertaken to develop, on an
experimental basis, a formalized theory of systems of beliefs and
their modifications. This theory uses the psycho-social concepts of
theories of cognitive consistency and of the tools of discrete
mathematics, such as rewriting and intervals within graphs. The axioms
and rewriting rules are elaborated from experimental data, and we
demonstrate that the system we have built has the property of
termination. This result is in accordance with experimental
observations that show that every subject having an inconsistent
system of beliefs (i.e., one containing contradictions) makes this
system evolve towards consistency to reach a simple, consistent
reference framework.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {141-154},
url = {http://www.dmtcs.org/proceedings/html/dmAB0112.abs.html}
}
@inproceedings{DMTCS-AB0113,
author = {Nazim Fat{\`e}s},
title = {Experimental study of Elementary Cellular Automata dynamics using the density parameter},
keywords = {Cellular Automata, Classification, Discrete Dynamical Systems, Density},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {Classifying cellular automata in order to capture the notion of chaos algorithmically is a challenging problem than can be tackled
in many ways. We here give a classification based on the computation
of a macroscopic parameter, the {${d}$}-spectrum, and show how
our classifying scheme can be used to separate the chaotic ECA from
the non-chaotic ones.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {155-166},
url = {http://www.dmtcs.org/proceedings/html/dmAB0113.abs.html}
}
@inproceedings{DMTCS-AB0114,
author = {Panama Geer and Harry W. McLaughlin and Keith Unsworth},
title = {Cellular Lines: An Introduction},
keywords = {cellular line definition, cellular array, string representation, derived string, line drawing algorithm},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {This paper provides a definition of a cellular line in a cellular array that is independent of the notion of a line in
{${R^{2}}$}. It also presents a way of determining whether or not a
cell set is a cellular line. Brief statements about existence,
uniqueness, and properties of cellular lines are included.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {167-178},
url = {http://www.dmtcs.org/proceedings/html/dmAB0114.abs.html}
}
@inproceedings{DMTCS-AB0115,
author = {Nick Anzalone and John Baldwin and Ilya Bronshtein and T. Kyle Petersen},
title = {A Reciprocity Theorem for Monomer-Dimer Coverings},
keywords = {reciprocity, monomer-dimer coverings, linear recurrences},
editor = {Michel Morvan and {\'E}ric R{\'e}mila},
booktitle = {Discrete Models for Complex Systems, DMCS'03},
abstract = {The problem of counting monomer-dimer coverings of a lattice is a longstanding problem in statistical mechanics. It has only been
exactly solved for the special case of dimer coverings in two
dimensions ([Ka61], [TF61]). In earlier work, Stanley
[St85] proved a reciprocity principle governing the number
N(m,n) of dimer coverings of an m by n rectangular grid
(also known as perfect matchings), where m is fixed and n is
allowed to vary. As reinterpreted by Propp [P01], Stanley's
result concerns the unique way of extending N(m,n) to n < 0 so
that the resulting bi-infinite sequence, N(m,n) for
n in ZZ, satisfies a linear recurrence relation with constant
coefficients. In particular, Stanley shows that N(m,n) is always
an integer satisfying the relation
N(m,-2-n) = epsilon N(m,n) where epsilon = 1 unless
m = 2(mod 4) and n is odd, in which case epsilon = -1.
Furthermore, Propp's method was applicable to higher-dimensional
cases. This paper discusses similar investigations of the numbers
M(m,n), of monomer-dimer coverings, or equivalently (not
necessarily perfect) matchings of an m by n rectangular grid.
We show that for each fixed m there is a unique way of extending
M(m,n) to n < 0 so that the resulting bi-infinite sequence,
M(m,n) for n in ZZ, satisfies a linear recurrence
relation with constant coefficients. We show that M(m,n),
a priori a rational number, is always an integer, using a
generalization of the combinatorial model offered by Propp.
Lastly, we give a new statement of reciprocity in terms of
multivariate generating functions from which Stanley's result
follows.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AB},
pages = {179-194},
url = {http://www.dmtcs.org/proceedings/html/dmAB0115.abs.html}
}
@inproceedings{DMTCS-AC0100,
author = {Cyril Banderier and Christian Krattenthaler},
title = {Discrete Random Walks 2003: Introduction and Acknowledgements },
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = {Presentation of the DRW2003 conference},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {1-8},
url = {http://www.dmtcs.org/proceedings/html/dmAC0100.abs.html}
}
@inproceedings{DMTCS-AC0101,
author = {Omer Angel},
title = {Random Infinite Permutations and the Cyclic Time Random Walk},
keywords = {Self interacting random walk, Random permutation, Phase transition},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { The random stirring process is a natural random walk on the set of
permutations of the vertex set of a graph. The cyclic time random walk is a
self interacting random walk on a graph. It is influenced by its past, in
that it is constrained to repeat its past choices if it returns to a
previously visited edge after a multiple of some period of time. The two
models are fundamentally equivalent to each other as well as to a certain
coalescence and fragmentation process.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {9-16},
url = {http://www.dmtcs.org/proceedings/html/dmAC0101.abs.html}
}
@inproceedings{DMTCS-AC0102,
author = {Nathana{\"e}l Berestycki and Rick Durrett},
title = {A phase transition in the random transposition random walk},
keywords = {random transposition, random graphs, phase transition, coagulation-fragmentation},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { Our work is motivated by Bourque-Pevzner's simulation study of the
effectiveness of the parsimony method in studying genome
rearrangement, and leads to a surprising result about the random
transposition walk in continuous time on the group of permutations on
n elements starting from the identity. Let {${D_{t}}$} be
the minimum number of transpositions needed to go back to the identity
element from the location at time {${t}$}. {${D_{t}}$}
undergoes a phase transition: for {${0 < c \le 1}$}, the
distance {${D_{cn/2} ~ cn/2}$}, i.e., the distance
increases linearly with time; for {${c > 1}$}, {${D_{cn/2} ~ u(c)n }$} where {${u}$} is an explicit function satisfying {${u(x)c^{*}}$}, the "distance" to feasibility is at least a positive
constant independent of {${n}$}. Our result is obtained using the combination of a
powerful local weak convergence method developed in Aldous [1992, 2000], Aldous
and Steele [2003], Steele [2002] and martingale techniques.
By exploiting a linear programming duality, our theorem implies the following result
in the context of sparse random graphs {${G(n, cn)}$} on {${n}$} nodes with
{${cn}$} edges, where edges are equipped with randomly generated weights.
Let {${M(n,c)}$} denote maximum weight matching in {${G(n, cn)}$}. We prove that when {${c}$} is a constant
and {${n{\rightarrow}{\infty}}$}, the limit {${lim_{n{\rightarrow}{\infty}} M(n,c)/n,}$}
exists, with high probability. We further extend this result to maximum weight {${b}$}-matchings also
in {${G(n,cn)}$}.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {113-126},
url = {http://www.dmtcs.org/proceedings/html/dmAC0111.abs.html}
}
@inproceedings{DMTCS-AC0112,
author = {Michael L. Green and Alan Krinik and Carrie Mortensen and Gerardo Rubino and Randall J. Swift},
title = {Transient Probability Functions: A Sample Path Approach},
keywords = {sample paths; dual processes; transient probability functions; Markov process; randomization.},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { A new approach is used to determine the transient probability functions of
Markov processes. This new solution method is a sample path counting
approach and uses dual processes and randomization. The approach is
illustrated by determining transient probability functions for a three-state
Markov process. This approach also provides a way to calculate transient
probability functions for Markov processes which have specific sample path
characteristics.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {127-136},
url = {http://www.dmtcs.org/proceedings/html/dmAC0112.abs.html}
}
@inproceedings{DMTCS-AC0113,
author = {Anders Karlsson},
title = {Some remarks concerning harmonic functions on homogeneous graphs},
keywords = {Discrete random walks, Dirichlet problem, radial variation, hyperbolic compactifications},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { We obtain a new result concerning harmonic functions on infinite
Cayley graphs {${X}$}: either every nonconstant harmonic function has
infinite radial variation in a certain uniform sense, or there is
a nontrivial boundary with hyperbolic properties at infinity of
{${X}$}. In the latter case, relying on a theorem of Woess, it follows
that the Dirichlet problem is solvable with respect to this
boundary. Certain relations to group cohomology are also discussed.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {137-144},
url = {http://www.dmtcs.org/proceedings/html/dmAC0113.abs.html}
}
@inproceedings{DMTCS-AC0114,
author = {Oleksiy Khorunzhiy},
title = {Rooted trees and moments of large sparse random matrices},
keywords = {Random matrices, spectral norm, rooted trees},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { In these expository paper we
describe the role of the rooted trees
as a base for convenient tools
in studies of random matrices.
Regarding the Wigner
ensemble of random matrices, we represent
main ingredients of this approach.
Also we refine our previous result on the
limit of the spectral norm of
adjacency matrix of large random graphs.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {145-154},
url = {http://www.dmtcs.org/proceedings/html/dmAC0114.abs.html}
}
@inproceedings{DMTCS-AC0115,
author = {Guy Louchard},
title = {The number of distinct part sizes of some multiplicity in compositions of an Integer. A probabilistic Analysis},
keywords = {Mellin transforms, urns models, Poissonization, saddle point method, generating functions},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { Random compositions of integers are used as theoretical models for many applications. The
degree of distinctness of a composition is a natural and important parameter.
A possible measure of distinctness is the number {${X}$} of distinct parts (or components).
This parameter has been analyzed in several papers. In this article we consider a variant
of the distinctness: the number {${X(m) }$} of distinct parts of multiplicity {${m}$} that we call
the {${m}$}-distinctness. A first motivation is a question asked by Wilf for random compositions: what is the asymptotic
value of the probability that a randomly chosen part size in a random composition of an
integer {${\nu }$} has multiplicity {${m}$}. This is related to {${\textbf{E}(X(m))}$}, which has been analyzed
by Hitczenko, Rousseau and Savage. Here, we investigate, from a probabilistic point of view, the
first full part, the maximum part size and the distribution of {${X(m)}$}.
We obtain asymptotically, as {${\nu {\rightarrow} {\infty}}$}, the moments and an expression for a continuous distribution {${\phi }$}, the (discrete)
distribution of {${X(m,\nu )}$} being computable from {${\phi }$}. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {155-170},
url = {http://www.dmtcs.org/proceedings/html/dmAC0115.abs.html}
}
@inproceedings{DMTCS-AC0116,
author = {Fabio P. Machado},
title = {Percolation on a non-homogeneous {P}oisson blob process},
keywords = {Poisson blob model, continuum percolation, phase transition, multi-scale percolation},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { We present the main results of a study for the
existence of vacant and occupied unbounded connected components in
a non-homogeneous Poisson blob process. The method used in the
proofs is a multi-scale percolation comparison.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {171-172},
url = {http://www.dmtcs.org/proceedings/html/dmAC0116.abs.html}
}
@inproceedings{DMTCS-AC0117,
author = {Philippe Marchal},
title = {Constructing a sequence of random walks strongly converging to {B}rownian motion},
keywords = {strong convergence, simple random walk, Brownian motion},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { We give an algorithm which constructs recursively a sequence of
simple random walks on {${\textbf{Z}}$} converging almost surely to a Brownian motion.
One obtains by the same method conditional versions of the simple random walk
converging to the excursion, the bridge, the meander or the normalized pseudobridge.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {181-190},
url = {http://www.dmtcs.org/proceedings/html/dmAC0117.abs.html}
}
@inproceedings{DMTCS-AC0118,
author = {James B. Martin},
title = {Reconstruction Thresholds on Regular Trees},
keywords = {broadcasting on a tree, reconstruction, hard-core model, Gibbs measure, extremality},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { We consider the model of broadcasting on a tree, with binary state space,
on the infinite rooted tree {${T^{k}}$} in which each node has {${k}$} children.
The root of the tree takes a random value 0 or 1, and then each node passes a value
independently to each of its children according to a 2x2 transition matrix {${\textbf{P}}$}.
We say that reconstruction is possible if the values at the {${d}$}th level of the tree
contain non-vanishing information about the value at the root as
{${d{\rightarrow}{\infty}}$}.
Extending a method of Brightwell and Winkler, we obtain new conditions under which reconstruction
is impossible, both in the general case and in the special case {${p_{11}=0}$}.
The latter case is closely related to the hard-core model from statistical physics;
a corollary of our results is that, for the hard-core model on the {${(k+1)}$}-regular tree
with activity {${\lambda =1}$}, the unique simple invariant Gibbs measure
is extremal in the set of Gibbs measures, for any {${k \ge 2}$}.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {191-204},
url = {http://www.dmtcs.org/proceedings/html/dmAC0118.abs.html}
}
@inproceedings{DMTCS-AC0119,
author = {Massimiliano Mattera},
title = {Annihilating random walks and perfect matchings of planar graphs},
keywords = {Perfect matchings, Partition fucntion, Interacting particles systems},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { We study annihilating random walks on {${Z}$} using techniques of
P.W. Kasteleyn and R. Kenyon on perfect matchings of planar graphs.
We obtain the asymptotic of the density of remaining particles and the partition function of the underlying statistical mechanical model.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {173-180},
url = {http://www.dmtcs.org/proceedings/html/dmAC0119.abs.html}
}
@inproceedings{DMTCS-AC0120,
author = {Mikhail Menshikov and Dimitri Petritis and Serguei Popov},
title = {Bindweeds or random walks in random environments on multiplexed trees and their asympotics},
keywords = {Markov chain, trees, random environment, recurrence criteria, matrix multiplicative cascades},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = {We report on the asymptotic behaviour of a new model of random walk, we term the bindweed model, evolving in a random
environment on an infinite multiplexed tree. The term multiplexed
means that the model can be viewed as a nearest neighbours random walk
on a tree whose vertices carry an internal degree of freedom from the
finite set {${\{1,...,d\}}$}, for some integer {${d}$}.
The consequence of the internal degree of freedom is an enhancement of
the tree graph structure induced by the replacement of ordinary edges
by multi-edges, indexed by the set {${\{1,...,d\} {\times}
\{1,...,d\}}$}. This indexing conveys the information on the
internal degree of freedom of the vertices contiguous to each edge.
The term random environment means that the jumping rates for the
random walk are a family of edge-indexed random variables, independent
of the natural filtration generated by the random variables entering
in the definition of the random walk; their joint distribution depends
on the index of each component of the multi-edges. We study the large
time asymptotic behaviour of this random walk and classify it with
respect to positive recurrence or transience in terms of a specific
parameter of the probability distribution of the jump rates. This
classifying parameter is shown to coincide with the critical value of
a matrix-valued multiplicative cascade on the ordinary tree (i.e. the
one without internal degrees of freedom attached to the vertices)
having the same vertex set as the state space of the random walk.
Only results are presented here since the detailed proofs will appear
elsewhere.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {205-216},
url = {http://www.dmtcs.org/proceedings/html/dmAC0120.abs.html}
}
@inproceedings{DMTCS-AC0121,
author = {Donatella Merlini},
title = {Generating functions for the area below some lattice paths},
keywords = {Generating functions, Riordan arrays, lattice paths, generating trees, area, internal path length.},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { We study some lattice paths related to the concept of generating trees.
When the matrix associated to this kind of trees is a Riordan array
{${D=(d(t),h(t))}$}, we are able to find the generating function for the total area
below these paths expressed in terms of the functions {${d(t)}$} and {${h(t).}$}},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {217-228},
url = {http://www.dmtcs.org/proceedings/html/dmAC0121.abs.html}
}
@inproceedings{DMTCS-AC0122,
author = {Saibal Mitra and Bernard Nienhuis},
title = {Osculating Random Walks on Cylinders},
keywords = {Random walks, {${O(n)}$} loop model},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { We consider random paths on a square lattice which take a left or a
right turn at every vertex. The possible turns are taken with equal
probability, except at a vertex which has been visited before.
In such case the vertex is left via the unused edge. When the initial
edge is reached the path is considered completed. We also consider
families of such paths which together cover every edge of the lattice
once and visit every vertex twice. Because these paths may touch but not
intersect each other and themselves, we call them osculating walks.
The ensemble of such families is also known as the dense {${O(n=1)}$} model.
We consider in particular such paths in a cylindrical geometry, with the
cylindrical axis parallel with one of the lattice directions. We
formulate a conjecture for the probability that a face of the lattice is
surrounded by {${m}$} distinct osculating paths. For even system sizes we
give a conjecture for
the probability that a path winds round the cylinder. For odd system
sizes we conjecture the probability that a point is visited by a path
spanning the infinite length of the cylinder.
Finally we conjecture an expression for the asymptotics of a binomial determinant},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {259-264},
url = {http://www.dmtcs.org/proceedings/html/dmAC0122.abs.html}
}
@inproceedings{DMTCS-AC0123,
author = {Nguy{\^e}n Th{\^e}, Michel},
title = {Area of {B}rownian Motion with Generatingfunctionology},
keywords = {Dyck path, Bernoulli random walk, Brownian motion, generating functions, weak convergence of stochastic processes.},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { This paper gives a survey of the limit distributions of the areas of
different types of random walks, namely Dyck paths,
bilateral Dyck paths, meanders, and Bernoulli random walks,
using the technology of generating functions only.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {229-242},
url = {http://www.dmtcs.org/proceedings/html/dmAC0123.abs.html}
}
@inproceedings{DMTCS-AC0124,
author = {Pierre Nicod{\`e}me},
title = {{${q}$}-gram analysis and urn models},
keywords = {Sequence comparison, Bernoulli model, urn models},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { Words of fixed size {${q}$} are commonly referred to as {${q}$}-grams.
We consider the problem of {${q}$}-gram filtration, a method commonly used
to speed up sequence comparison. We are interested in the
statistics of the number of {${q}$}-grams common to two random texts
(where multiplicities are not counted) in
the non uniform Bernoulli model. In the exact and dependent model,
when omitting border effects,
a {${q}$}-gram in a random sequence depends on the {${q-1}$}
preceding {${q}$}-grams. In an approximate and independent model, we draw
randomly a {${q}$}-gram at each position, independently of the others
positions. Using ball and urn models, we analyze the independent
model. Numerical simulations show that this model is an excellent
first order approximation to the dependent model. We provide an
algorithm to compute the moments.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {243-258},
url = {http://www.dmtcs.org/proceedings/html/dmAC0124.abs.html}
}
@inproceedings{DMTCS-AC0125,
author = {Alois Panholzer},
title = {Non-crossing trees revisited: cutting down and spanning subtrees},
keywords = {Non-crossing trees, generating function, limiting distributions},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { Here we consider two parameters for random non-crossing trees: \emph{(i)} the number of random cuts
to destroy a size-{${n}$} non-crossing tree and \emph{(ii)} the spanning subtree-size of {${p}$}
randomly chosen nodes in a size-{${n}$} non-crossing tree. For both quantities, we are able
to characterise for {${n {\rightarrow} {\infty}}$} the limiting distributions. Non-crossing trees are
almost conditioned Galton-Watson trees, and it has been already shown,
that the contour and other usually associated discrete excursions converge,
suitable normalised, to the Brownian excursion.
We can interpret parameter \emph{(ii)} as a functional of a conditioned
random walk, and although we do not have such an interpretation for parameter \emph{(i)},
we obtain here limiting distributions, that are also arising as limits of some functionals
of conditioned random walks.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {265-276},
url = {http://www.dmtcs.org/proceedings/html/dmAC0125.abs.html}
}
@inproceedings{DMTCS-AC0126,
author = {Serguei Yu. Popov},
title = {Frogs and some other interacting random walks models},
keywords = {simple random walk, critical probability, shape theorem, recurrence},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { We review some recent results for a system of
simple random walks on graphs, known as \emph{frog model}.
Also, we discuss several modifications of this model, and present a few open problems.
A simple version of the frog model can
be described as follows: There are active and
sleeping particles living on some graph. Each active particle
performs a simple random walk with discrete time and at each moment
it may disappear with probability {${1-p}$}. When an active particle
hits a sleeping particle, the latter becomes active.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {277-288},
url = {http://www.dmtcs.org/proceedings/html/dmAC0126.abs.html}
}
@inproceedings{DMTCS-AC0127,
author = {Klaus Simon and Beat Trachsler},
title = {A Random Walk Approach for Light Scattering in Material},
keywords = {Random Walk, Kubelka-Munk, Light Scattering, First-Passage Time Probability, Narayana Numbers, Catalan Numbers, Chebyshev Polynomials},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { Understanding reflection is one of the key competences in graphic
arts industry. A very popular approach was given by
Kubelka and Munk [1931] who derived a simple relationship
between the scattering and absorption coefficients and the overall
reflectance. This paper presents an alternative approach which
describes the behavior of light in matter as a special kind of random
walk.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {289-300},
url = {http://www.dmtcs.org/proceedings/html/dmAC0127.abs.html}
}
@inproceedings{DMTCS-AC0128,
author = {Andr{\'a}s Telcs},
title = {The volume and time comparison principle and transition probability estimates for random walks},
keywords = {random walks, heat kernel estimates},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { This paper presents necessary and sufficient conditions for on-
and off-diagonal transition probability estimates for random
walks on weighted graphs. On the integer lattice and on may
fractal type graphs both the volume of a ball and the mean exit
time from a ball are independent of the center, uniform in space.
Here the upper estimate is given without such restriction and
two-sided estimate is given if the mean exit time is independent
of the center but the volume is not.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {301-308},
url = {http://www.dmtcs.org/proceedings/html/dmAC0128.abs.html}
}
@inproceedings{DMTCS-AC0129,
author = {Leonid Tolmatz},
title = {The Saddle Point Method for the Integral of the Absolute Value of the Brownian Motion},
keywords = {Brownian motion, distribution, moments, asymptotics, saddle point, Airy functions.},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { The distribution function of the integral of the absolute value
of the Brownian motion was expressed by L.Tak{\'a}cs in the form of
various series.
In the present paper we determine the exact tail asymptotics of
this distribution function. The proposed method is applicable to a variety
of other Wiener functionals as well.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {309-324},
url = {http://www.dmtcs.org/proceedings/html/dmAC0129.abs.html}
}
@inproceedings{DMTCS-AC0130,
author = {Valentin Topchii and Vladimir Vatutin},
title = {Individuals at the origin in the critical catalytic branching random walk},
keywords = {catalytic branching random walk; critical two-dimensional Bellman-Harris process},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { A continuous time branching random walk on the lattice {${\textbf{Z}}$}
is considered in which individuals may produce children at the
origin only. Assuming that the underlying random walk is symmetric
and the offspring reproduction law is critical we prove a
conditional limit theorem for the number of individuals at the
origin.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {325-332},
url = {http://www.dmtcs.org/proceedings/html/dmAC0130.abs.html}
}
@inproceedings{DMTCS-AC0131,
author = {Alessandro Vezzani and Davide Cassi and Raffaella Burioni},
title = {Average properties of combinatorial problems and thermodynamics of spin models on graphs},
keywords = {statistical mechanics, graphs, random-walks, percolation},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { The study of thermodynamic properties of
classical spin models on infinite graphs naturally leads to consider the new
combinatorial problems of random-walks and percolation on the average.
Indeed, spin models with {${O(n)}$}
continuous symmetry present spontaneous magnetization only on
transient on the average graphs, while models
with discrete symmetry (Ising and Potts) are spontaneously magnetized on
graphs exhibiting percolation on the
average. In this paper we define the combinatorial problems on the average,
showing that they give rise to classifications
of graph topology which are different from the ones obtained in usual
(local) random-walks and percolation. Furthermore,
we illustrate the theorem proving the correspondence between
Potts model and average percolation.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2003,
volume = {AC},
pages = {333-344},
url = {http://www.dmtcs.org/proceedings/html/dmAC0131.abs.html}
}
@inproceedings{DMTCS-AC0132,
author = {Nisheeth Vishnoi},
title = {Non Uniform Random Walks},
keywords = {Non uniform random walk},
editor = {Cyril Banderier and Christian Krattenthaler},
booktitle = {Discrete Random Walks, DRW'03},
abstract = { Given {${\epsilon _{i} {\in} [0,1)}$} for each {${1 < i < n,}$}
a particle performs the following random walk on {${\{1,2,...,n\}}$}:\par
If the particle is at {${n}$}, it chooses a point uniformly at random (u.a.r.)
from {${\{1,...,n-1\}.}$} If the current position of the particle is {${m}$} ({${1 i.}$}
Then we show that for the following parameterized family of {${\epsilon }$}'s:
{${\epsilon _{i} = (n-i) / (n-i+ \alpha {\cdot} (i-1)) , 1***1}$}.
In our new, generalized version of AIMD, the choice of users to have
their
allocations cut is determined by a selection rule whereby the
probabilities of selection
are proportional to {${x_{i}^{\alpha }(t)/
\sum_{j}
x_{j}^{\alpha }}$}, with {${\alpha }$} a
parameter
of the policy. Variations of parameters allows one to adjust fairness
under AIMD (as
measured for example by the variance of {${x_{i}(t)}$})
as
well as to provide for differentiated service. The primary
contribution
here is an asymptotic, large-{${N}$} analysis of the above
nonlinear
AIMD algorithm within a baseline mathematical model that leads to
explicit
formulas for the density function governing the allocations
{${x_{i}(t)}$}
in statistical equilibrium. The analysis yields explicit formulas for
measures
of fairness and several techniques for supplying differentiated
service via AIMD. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {27-38},
url = {http://www.dmtcs.org/proceedings/html/dmAD0104.abs.html}
}
@inproceedings{DMTCS-AD0105,
author = {Daniel Berend and Vladimir Braverman},
title = {Convex hull for intersections of random lines},
keywords = {convex hull, random lines},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { The problem of finding the convex hull of the intersection points of
random
lines was studied in {[dt]} and {[new]}, and
algorithms
with expected linear time were found. We improve the previous results
of
the model in {[dt]} by giving a universal algorithm for a
wider range of distributions. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {39-48},
url = {http://www.dmtcs.org/proceedings/html/dmAD0105.abs.html}
}
@inproceedings{DMTCS-AD0106,
author = {Cary Cherng and Richard E. Ladner},
title = {Cache efficient simple dynamic programming},
keywords = {Dynamic Programming, Cache-Oblivious Algorithms, Cache-Aware Algorithms},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { New cache-oblivious and cache-aware algorithms for simple dynamic
programming
based on Valiant's context-free language recognition algorithm are
designed,
implemented, analyzed, and empirically evaluated with timing studies
and
cache simulations. The studies show that for large inputs the
cache-oblivious
and cache-aware dynamic programming algorithms are significantly
faster than the standard dynamic programming algorithm. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {49-58},
url = {http://www.dmtcs.org/proceedings/html/dmAD0106.abs.html}
}
@inproceedings{DMTCS-AD0107,
author = {Christian Costermans and Jean-Yves Enjalbert and Hoang Ngoc Minh},
title = {Algorithmic and combinatoric aspects of multiple harmonic sums},
keywords = {polylogarithms, polyz{\^e}tas, multiple harmonic sums, singular expansion, shuffle algebra, Lyndon words},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { Ordinary generating series of \emph{multiple} harmonic sums admit a
\emph{full}
singular expansion in the basis of functions \par
{${\{(1-z)^{\alpha }\textit{log}^{\beta }(1-z)\}_{\alpha {\in}{\integers},
\beta {\in}{\naturals}}}$}, near the singularity
{${z=1}$}.
A \emph{constructive} proof of this result is given, and, by
\emph{combinatoric}
aspects, an explicit evaluation of Taylor coefficients of functions in
some
\emph{polylogarithmic} algebra is obtained. In particular, the
\emph{asymptotic
expansion} of multiple harmonic sums is easily deduced. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {59-70},
url = {http://www.dmtcs.org/proceedings/html/dmAD0107.abs.html}
}
@inproceedings{DMTCS-AD0108,
author = {Beno\^{\i}t Daireaux and V{\'e}ronique Maume-Deschamps and Brigitte Vall{\'e}e},
title = {The {L}yapunov tortoise and the dyadic hare},
keywords = { },
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { We study a gcd algorithm directed by Least Significant Bits, the
so--called
LSB algorithm, and provide a precise average--case analysis of its
main
parameters [number of iterations, number of shifts, etc{\ldots}]. This
analysis
is based on a precise study of the dynamical systems which provide a
continuous
extension of the algorithm, and, here, it is proved convenient to use
both
a 2--adic extension and a real one. This leads to the framework of
products
of random matrices, and our results thus involve a constant
{${\gamma }$}
which is the Lyapunov exponent of the set of matrices relative to the
algorithm.
The algorithm can be viewed as a race between a dyadic hare with a
speed
of 2 bits by step and a ``real'' tortoise with a speed equal to {${
\gamma /\textit{log}2
\sim 0.05}$} bits by step. Even if the tortoise starts before the
hare,
the hare easily catches up with the tortoise [unlike in Aesop's fable
[Ae]{\ldots}], and the algorithm terminates. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {71-94},
url = {http://www.dmtcs.org/proceedings/html/dmAD0108.abs.html}
}
@inproceedings{DMTCS-AD0109,
author = {Julien Fayolle and Mark Daniel Ward},
title = {Analysis of the average depth in a suffix tree under a {M}arkov model},
keywords = {Suffix trees, depth, average analysis, asymptotics, analytic methods},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { In this report, we prove that under a Markovian model of order one,
the
average depth of suffix trees of index {${n}$} is asymptotically
similar
to the average depth of tries (a.k.a. digital trees) built on
{${n}$}
independent strings. This leads to an asymptotic behavior of
{${(\textit{log}n)/h
+ C}$} for the average of the depth of the suffix tree, where
{${h}$}
is the entropy of the Markov model and {${C}$} is constant. Our
proof
compares the generating functions for the average depth in tries and
in
suffix trees; the difference between these generating functions is
shown
to be asymptotically small. We conclude by using the asymptotic
behavior
of the average depth in a trie under the Markov model found by Jacquet
and Szpankowski ([JaSz91]). },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {95-104},
url = {http://www.dmtcs.org/proceedings/html/dmAD0109.abs.html}
}
@inproceedings{DMTCS-AD0110,
author = {James Allen Fill and Nevin Kapur},
title = {A repertoire for additive functionals of uniformly distributed {${m}$}-ary search trees},
keywords = {additive functionals, Hadamard products, limit laws, method of moments, search trees, shape functional, singularity analysis, space requirement, leaves},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { Using recent results on singularity analysis for Hadamard products of
generating
functions, we obtain the limiting distributions for additive
functionals
on {${m}$}-ary search trees on {${n}$} keys with
toll
sequence (i)\ {${n^{\alpha }}$} with
{${\alpha \ge 0}$}
({${\alpha =0}$} and {${\alpha =1}$} correspond roughly
to
the space requirement and total path length, respectively);
(ii)\ {${{ln}
\binom{n}{ m-1}}$}, which corresponds to the
so-called shape functional;
and (iii)\ {${\textbf{1}_{n=m-1}}$}, which
corresponds to the number of leaves. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {105-114},
url = {http://www.dmtcs.org/proceedings/html/dmAD0110.abs.html}
}
@inproceedings{DMTCS-AD0111,
author = {Mihai Furis and Pawe{\l} Hitczenko and Jeremy Johnson},
title = {Cache miss analysis of {WHT} algorithms},
keywords = {Cache, Divide and Conquer Recurrences, Geometric Distributions, Memory Access Patterns, Performance Analysis, Random Compositions, Walsh-Hadamard Transform},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { On modern computers memory access patterns and cache utilization are
as
important, if not more important, than operation count in obtaining
high-performance
implementations of algorithms. In this work, the memory behavior of a
large
family of algorithms for computing the Walsh-Hadamard transform, an
important
signal processing transform related to the fast Fourier transform, is
investigated.
Empirical evidence shows that the family of algorithms exhibit a wide
range
of performance, despite the fact that all algorithms perform the same
number
of arithmetic operations. Different algorithms, while having the same
number
of memory operations, access memory in different patterns and
consequently
have different numbers of cache misses. A recurrence relation is
derived
for the number of cache misses and is used to determine the
distribution of cache misses over the space of WHT algorithms. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {115-124},
url = {http://www.dmtcs.org/proceedings/html/dmAD0111.abs.html}
}
@inproceedings{DMTCS-AD0112,
author = {{\'E}ric Fusy},
title = {Quadratic exact-size and linear approximate-size random generation of planar graphs},
keywords = {planar graphs, Boltzmann samplers, rejection sampling},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { This extended abstract introduces a new algorithm for the random
generation of labelled planar graphs. Its principles rely on
Boltzmann samplers as recently developed by Duchon, Flajolet,
Louchard, and Schaeffer. It combines the Boltzmann framework, a
judicious use of rejection, a new combinatorial bijection found by
Fusy, Poulalhon and Schaeffer, as well as a precise analytic
description of the generating functions counting planar graphs,
which was recently obtained by Gim{\'e}nez and Noy. This gives
rise to an extremely efficient algorithm for the random generation
of planar graphs. There is a preprocessing step of some fixed small
cost. Then, for each generation, the time complexity is quadratic
for exact-size uniform sampling and linear for approximate-size
sampling. This greatly improves on the best previously known time
complexity for exact-size uniform sampling of planar graphs with
{${n}$} vertices, which was a little over
{${\mathcal{O}(n^{7})}$}.},
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {125-138},
url = {http://www.dmtcs.org/proceedings/html/dmAD0112.abs.html}
}
@inproceedings{DMTCS-AD0113,
author = {Dani{\`e}le Gardy and Alan Woods},
title = {And/or tree probabilities of Boolean functions},
keywords = {And/Or tree, Boolean formula, tautology, tree enumeration},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { We consider two probability distributions on Boolean functions defined
in
terms of their representations by \textit{and/or} trees (or formulas).
The
relationships between them, and connections with the complexity of the
function,
are studied. New and improved bounds on these probabilities are given
for
a wide class of functions, with special attention being paid to the
constant
function \textit{True} and read-once functions in a fixed number
of variables. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {139-146},
url = {http://www.dmtcs.org/proceedings/html/dmAD0113.abs.html}
}
@inproceedings{DMTCS-AD0114,
author = {Omer Gim{\'e}nez and Marc Noy},
title = {The number of planar graphs and properties of random planar graphs},
keywords = {Planar graph, random graph, asymptotic enumeration, limit law, normal law, analytic combinatorics.},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { We show an asymptotic estimate for the number of labelled planar
graphs
on {${n}$} vertices. We also find limit laws for the number of
edges,
the number of connected components, and other parameters in random
planar graphs. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {147-156},
url = {http://www.dmtcs.org/proceedings/html/dmAD0114.abs.html}
}
@inproceedings{DMTCS-AD0115,
author = {Fr{\'e}d{\'e}ric Giroire},
title = {Order statistics and estimating cardinalities of massive data sets},
keywords = {cardinality, estimates, very large multiset, traffic analysis},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { We introduce a new class of algorithms to estimate the cardinality of
very
large multisets using constant memory and doing only one pass on the
data.
It is based on order statistics rather that on bit patterns in binary
representations
of numbers. We analyse three families of estimators. They attain a
standard
error of {${1/\sqrt{M}}$} using
{${M}$}
units of storage, which places them in the same class as the best
known
algorithms so far. They have a very simple internal loop, which gives
them
an advantage in term of processing speed. The algorithms are validated
on internet traffic traces. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {157-166},
url = {http://www.dmtcs.org/proceedings/html/dmAD0115.abs.html}
}
@inproceedings{DMTCS-AD0116,
author = {Bernhard Gittenberger},
title = {The profile of unlabeled trees},
keywords = {unlabeled trees, profile, Brownian excursion, local time},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { We consider the number of nodes in the levels of unlabeled rooted
random
trees and show that the joint distribution of several level sizes
(where
the level number is scaled by {${\sqrt{n}}$}) weakly
converges
to the distribution of the local time of a Brownian excursion
evaluated
at the times corresponding to the level numbers. This extends existing
results
for simply generated trees and forests to the case of unlabeled rooted
trees. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {167-172},
url = {http://www.dmtcs.org/proceedings/html/dmAD0116.abs.html}
}
@inproceedings{DMTCS-AD0117,
author = {Bernhard Gittenberger and Alois Panholzer},
title = {Some results for monotonically labelled simply generated trees},
keywords = {simply generated trees, monotone labellings, node depth, leaf height},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { We consider simply generated trees, where the nodes are equipped with
weakly
monotone labellings with elements of {${\{1, 2, {\ldots},
r\}}$},
for {${r}$} fixed. These tree families were introduced in
[ProUrb1983]
and studied further in [Kir1984], [Bli1987], and [MorPro2005]. Here we
give
distributional results for several tree statistics (the depth of a
random
node, the ancestor-tree size and the Steiner-distance of
{${p}$}
randomly chosen nodes, the height of the {${j}$}-st leaf, and
the
number of nodes with label {${l}$}), which extend the existing
results
and also contain the corresponding results for unlabelled simply
generated trees as the special case {${r=1}$}. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {173-180},
url = {http://www.dmtcs.org/proceedings/html/dmAD0117.abs.html}
}
@inproceedings{DMTCS-AD0118,
author = {Rudolf Gr{\"u}bel},
title = {A hooray for Poisson approximation},
keywords = {binary search tree, multiplicity of maxima, tree profile},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { We give several examples for Poisson approximation of quantities of
interest
in the analysis of algorithms: the distribution of node depth in a
binary
search tree, the distribution of the number of losers in an election
algorithm
and the discounted profile of a binary search tree. A simple and
well-known
upper bound for the total variation distance between the distribution
of
a sum of independent Bernoulli variables and the Poisson distribution
with
the same mean turns out to be very useful in all three cases. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {181-192},
url = {http://www.dmtcs.org/proceedings/html/dmAD0118.abs.html}
}
@inproceedings{DMTCS-AD0119,
author = {Hsien-Kuei Hwang},
title = {Profiles of random trees: plane-oriented recursive trees},
keywords = {Plane-oriented recursive trees, profile of trees, limit distribution, convergence of all moments, total path length, random binary trees},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { We summarize several limit results for the profile of random
plane-oriented
recursive trees. These include the limit distribution of the
normalized
profile, asymptotic bimodality of the variance, asymptotic
approximations
of the expected width and the correlation coefficients of two level
sizes.
We also unveil an unexpected connection between the profile of
plane-oriented
recursive trees (with logarithmic height) and that of random binary
trees
(with height proportional to the square root of tree size). },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {193-200},
url = {http://www.dmtcs.org/proceedings/html/dmAD0119.abs.html}
}
@inproceedings{DMTCS-AD0120,
author = {Predrag R. Jelenkovi{\'c} and Xiaozhu Kang and Ana Radovanovi{\'c}},
title = {Near optimality of the discrete persistent access caching algorithm},
keywords = {persistent-access-caching, least-recently-used caching, least-frequently-used caching, move-to-front searching, generalized Zipf's law distributions, heavy-tailed distributions, Web caching, cache fault probability, average-case analysis},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { Renewed interest in caching techniques stems from their application to
improving
the performance of the World Wide Web, where storing popular documents
in
proxy caches closer to end-users can significantly reduce the document
download
latency and overall network congestion. Rules used to update the
collection
of frequently accessed documents inside a cache are referred to as
cache
replacement algorithms. Due to many different factors that influence
the
Web performance, the most desirable attributes of a cache replacement
scheme
are low complexity and high adaptability to variability in Web access
patterns.
These properties are primarily the reason why most of the practical
Web
caching algorithms are based on the easily implemented
Least-Recently-Used
(LRU) cache replacement heuristic. In our recent paper [JERA04tr], we
introduce
a new algorithm, termed Persistent Access Caching (PAC), that, in
addition
to desirable low complexity and adaptability, somewhat surprisingly
achieves
nearly optimal performance for the independent reference model and
generalized
Zipf's law request probabilities. Two drawbacks of the PAC algorithm
are
its dependence on the request arrival times and variable storage
requirements.
In this paper, we resolve these problems by introducing a discrete
version
of the PAC policy (DPAC) that, after a cache miss, places the
requested
document in the cache only if it is requested at least {${k}$}
times
among the last {${m}$}, {${m\ge k}$}, requests. However,
from
a mathematical perspective, due to the inherent coupling of the
replacement
decisions for different documents, the DPAC algorithm is considerably
harder
to analyze than the original PAC policy. In this regard, we develop a
new
analytical technique for estimating the performance of the DPAC rule.
Using
our analysis, we show that this algorithm is close to optimal even for
small
values of {${k}$} and {${m}$}, and, therefore, adds
negligible
additional storage and processing complexity in comparison to the
ordinary LRU policy. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {201-222},
url = {http://www.dmtcs.org/proceedings/html/dmAD0120.abs.html}
}
@inproceedings{DMTCS-AD0121,
author = {Gerard Kok},
title = {Pattern distribution in various types of random trees},
keywords = {random trees, generating functions, limiting distributions},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { Let {${T_{n}}$} denote the set of unrooted unlabeled
trees
of size {${n}$} and let {${M_{k}}$} be a
particular
(finite) tree. Assuming that every tree of {${T_{n}}$}
is
equally likely, it is shown that the number of occurrences
{${X_{n}}$}
of {${M_{k}}$} as an induced sub-tree satisfies
{${{E}
X_{n} \sim {\mu}n}$} and {${\textit{Var} X_{n}
\sim \sigma ^{2}
n}$} for some (computable) constants {${{\mu}> 0}$} and
{${\sigma \ge 0}$}.
Furthermore, if {${\sigma >0}$} then {${(X_{n} -
\textit{E}
X_{n})/\sqrt{Var} X_{n}}$}
converges to a limiting distribution with
density {${(A+Bt^{2})e^{-Ct^{2}}}$} for
some
constants {${A,B,C}$}. However, in all cases in which we were
able
to calculate these constants, we obtained {${B=0}$} and thus a
normal
distribution. Further, if we consider planted or rooted trees instead
of
{${T_{n}}$} then the limiting distribution is always
normal.
Similar results can be proved for planar, labeled and simply generated
trees. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {223-230},
url = {http://www.dmtcs.org/proceedings/html/dmAD0121.abs.html}
}
@inproceedings{DMTCS-AD0122,
author = {Guy Louchard and Helmut Prodinger and Mark Daniel Ward},
title = {The number of distinct values of some multiplicity in sequences of geometrically distributed random variables},
keywords = {Distinct values, geometric random variables, extreme value distribution},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { We consider a sequence of {${n}$} geometric random variables
and
interpret the outcome as an urn model. For a given parameter
{${m}$},
we treat several parameters like what is the largest urn containing at
least
(or exactly) {${m}$} balls, or how many urns contain at least
{${m}$}
balls, etc. Many of these questions have their origin in some computer
science
problems. Identifying the underlying distributions as (variations of)
the
extreme value distribution, we are able to derive asymptotic
equivalents
for all (centered or uncentered) moments in a fairly automatic way. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {231-256},
url = {http://www.dmtcs.org/proceedings/html/dmAD0122.abs.html}
}
@inproceedings{DMTCS-AD0123,
author = {Pierre Nicod{\`e}me},
title = {Average profiles, from tries to suffix-trees},
keywords = {tries, suffix-trees, profile, asymptotics, Mellin transform, saddle-point method.},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { We build upon previous work of\ [Fayj04] and\ [ParSzp05] to
study
asymptotically the average internal profile of tries and of
suffix-trees.
The binary keys and the strings are built from a Bernoulli source
{${(p,q)}$}. We consider
the average number {${p_{k,\textit{P}}(\nu )}$} of
internal
nodes at depth {${k}$} of a trie whose number of input keys
follows
a Poisson law of parameter {${\nu }$}. The Mellin transform of
the
corresponding bivariate generating function has a major singularity at
the
origin, which implies a phase reversal for the saturation rate
{${p_{k,\textit{P}}(\nu )/2^{k}}$} as {${k}$} reaches the value
{${2\textit{log}(\nu )/(\textit{log}(1/p)+\textit{log}(1/q))}$}. We
prove
that the asymptotic average profiles of random tries and suffix-trees
are
mostly similar, up to second order terms, a fact that has been
experimentally
observed in\ [Nic03]; the proof follows from comparisons to the
profile of tries in the Poisson model. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {257-266},
url = {http://www.dmtcs.org/proceedings/html/dmAD0123.abs.html}
}
@inproceedings{DMTCS-AD0124,
author = {Gahyun Park and Wojciech Szpankowski},
title = {Analysis of biclusters with applications to gene expression data },
keywords = {Random matrix, two-dimensional patterns, bicluster, microarray data, biclique.},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { For a given matrix of size {${n × m}$} over a finite alphabet
{${\textit{A}}$},
a bicluster is a submatrix composed of selected columns and rows
satisfying
a certain property. In microarrays analysis one searches for largest
biclusters
in which selected rows constitute the same string (pattern); in
another
formulation of the problem one tries to find a maximally dense
submatrix.
In a conceptually similar problem, namely the bipartite clique problem
on
graphs, one looks for the largest binary submatrix with all
`{${1}$}'.
In this paper, we assume that the original matrix is generated by a
memoryless
source over a finite alphabet {${\textit{A}}$}. We first consider
the
case where the selected biclusters are square submatrices and prove
that
with high probability (whp) the largest (square) bicluster having the
same
row-pattern is of size {${\textit{log}_{Q}^{2} n
m}$}
where {${Q^{-1}}$} is the (largest) probability of a
symbol.
We observe, however, that when we consider \emph{any} submatrices
(not
just \emph{square} submatrices), then the largest area of a
bicluster
jumps to {${A n}$} (whp) where {${A}$} is an explicitly
computable
constant. These findings complete some recent results concerning
maximal
biclusters and maximum balanced bicliques for random bipartite graphs. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {267-274},
url = {http://www.dmtcs.org/proceedings/html/dmAD0124.abs.html}
}
@inproceedings{DMTCS-AD0125,
author = {Nicolas Pouyanne},
title = {Classification of large P{\'o}lya-Eggenberger urns with regard to their asymptotics},
keywords = { },
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { This article deals with P{\'o}lya generalized urn models with
constant
balance in any dimension. It is based on the algebraic approach of
[AlgApproach]
and classifies urns having ``large'' eigenvalues in five classes,
depending
on their almost sure asymptotics. These classes are described in terms
of
the spectrum of the urn's replacement matrix and examples of each case
are
treated. We study the cases of so-called cyclic urns in any dimension
and
{${m}$}-ary search trees for {${m \ge 27}$}. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {275-286},
url = {http://www.dmtcs.org/proceedings/html/dmAD0125.abs.html}
}
@inproceedings{DMTCS-AD0126,
author = {Hadas Shachnai and Lisa Zhang},
title = {The master ring problem},
keywords = {Master ring, shortest common supersequence, optical networks, exact algorithms.},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { We consider the \emph{master ring problem (MRP)} which often arises
in
optical network design. Given a network which consists of a collection
of interconnected
rings {${R_{1}}$}, {${{\ldots}}$},
{${R_{K}}$},
with {${n_{1}}$}, {${{\ldots}}$},
{${n_{K}}$}
distinct nodes, respectively, we need to find an ordering of the nodes
in
the network that respects the ordering of every individual ring, if
one
exists. Our main result is an exact algorithm for MRP whose running
time
approaches {${Q{\cdot}\prod _{k=1}^{K}
(n_{k}/\sqrt{2})}$}
for some polynomial {${Q}$}, as the {${n_{k}}$}
values
become large. For the \emph{ring clearance problem}, a special case
of
practical interest, our algorithm achieves this running time for rings
of
\emph{any} size {${n_{k} \ge 2}$}. This yields the
first nontrivial
improvement, by factor of {${(2\sqrt{2})^{K}
\approx
(2.82)^{K}}$}, over the running time of the naive
algorithm, which
exhaustively enumerates all {${\prod _{k=1}^{K}
(2n_{k})}$} possible solutions. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {287-296},
url = {http://www.dmtcs.org/proceedings/html/dmAD0126.abs.html}
}
@inproceedings{DMTCS-AD0127,
author = {Alfredo Viola},
title = {Distributional analysis of Robin Hood linear probing hashing with buckets},
keywords = {Distributional Analysis, Hashing, Linear Probing, Buckets},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { This paper presents the first distributional analysis of a linear
probing
hashing scheme with buckets of size {${b}$}. The exact
distribution
of the cost of successful searches for a {${b\alpha }$}-full
table
is obtained, and moments and asymptotic results are derived. With the
use
of the Poisson transform distributional results are also obtained for
tables
of size {${m}$} and {${n}$} elements. A key element in
the
analysis is the use of a new family of numbers that satisfies a
recurrence
resembling that of the Bernoulli numbers. These numbers may prove
helpful
in studying recurrences involving truncated generating functions, as
well as in other problems related with buckets. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {297-306},
url = {http://www.dmtcs.org/proceedings/html/dmAD0127.abs.html}
}
@inproceedings{DMTCS-AD0128,
author = {Mark Daniel Ward and Wojciech Szpankowski},
title = {Analysis of the multiplicity matching parameter in suffix trees},
keywords = {suffix trees, combinatorics on words, pattern matching, autocorrelation polynomial, complex asymptotics, data compression},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { In a suffix tree, the multiplicity matching parameter (MMP)
{${M_{n}}$}
is the number of leaves in the subtree rooted at the branching point
of
the {${(n+1)}$}st insertion. Equivalently, the MMP is the
number
of pointers into the database in the Lempel-Ziv '77 data compression
algorithm.
We prove that the MMP asymptotically follows the logarithmic series
distribution
plus some fluctuations. In the proof we compare the distribution of
the
MMP in suffix trees to its distribution in tries built over
independent
strings. Our results are derived by both probabilistic and analytic
techniques
of the analysis of algorithms. In particular, we utilize combinatorics
on
words, bivariate generating functions, pattern matching, recurrence
relations,
analytical poissonization and depoissonization, the Mellin transform,
and complex analysis. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {307-322},
url = {http://www.dmtcs.org/proceedings/html/dmAD0128.abs.html}
}
@inproceedings{DMTCS-AD0129,
author = {Mark C. Wilson},
title = {Asymptotics of Riordan arrays},
keywords = {bivariate asymptotics, generating function},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { The machinery of Riordan arrays has been used recently by several
authors.
We show how meromorphic singularity analysis can be used to provide
uniform
bivariate asymptotic expansions, in the central regime, for a
generalization
of these arrays. We show how to do this systematically, for various
descriptions
of the array. Several examples from recent literature are given. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {323-334},
url = {http://www.dmtcs.org/proceedings/html/dmAD0129.abs.html}
}
@inproceedings{DMTCS-AD0130,
author = {Daniel Berend and Ephraim Korach and Shira Zucker},
title = {Two-anticoloring of planar and related graphs},
keywords = {Graph, algorithm, combinatorial optimization, graph anticoloring, separation},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { An \textit{anticoloring} of a graph is a coloring of some of the
vertices,
such that no two adjacent vertices are colored in distinct colors. We
deal
with the anticoloring problem with two colors for planar graphs, and,
using
Lipton and Tarjan's separation algorithm, provide an algorithm with
some
bound on the error. In the particular cases of graphs which are strong
products
of two paths or two cycles, we provide an explicit optimal solution. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {335-342},
url = {http://www.dmtcs.org/proceedings/html/dmAD0130.abs.html}
}
@inproceedings{DMTCS-AD0131,
author = {Charlotte Brennan and Arnold Knopfmacher},
title = {The distribution of ascents of size {${d}$} or more in samples of geometric random variables},
keywords = {geometric random variables, distributions, generating functions},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = {We consider words or strings of characters {${a_{1}a_{2}a_{3}{\cdots}a_{n}}$} of length {${n}$}, where the letters {${a_{i}
{\in}{\integers}}$}
are independently generated with a geometric probability
{${\mathbb{P}\{X=k\}=pq^{k-1}}$}
where {${p+q=1.}$}
\par
Let {${d}$} be a fixed
nonnegative
integer. We say that we have an ascent of size {${d}$} or more
if
{${a_{i+1} \ge a_{i}+d}$}. We determine
the
mean, variance and limiting distribution of the number of ascents of
size
{${d}$} or more in a random geometrically distributed word. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AD},
pages = {343-352},
url = {http://www.dmtcs.org/proceedings/html/dmAD0131.abs.html}
}
@inproceedings{DMTCS-AD0132,
author = {Amr Elmasry},
title = {Distribution-sensitive set multi-partitioning},
keywords = {algorithm analysis and design; distribution-sensitive algorithms; output-sensitive algorithms; lower bounds},
editor = {Conrado Mart\'{\i}nez},
booktitle = {2005 International Conference on Analysis of Algorithms},
abstract = { Given a set {${\textit{S}}$} with real-valued members, associated
with
each member one of two possible types; a multi-partitioning of
{${\textit{S}}$}
is a sequence of the members of {${\textit{S}}$} such that if
{${x,y
{\in}\textit{S}}$} have different types and {${xA
\cap B|{\geq}b}$},
{${|A \cap B| {\geq}c}$}, and {${|A
\cap B|{\geq}d}$}.\par By symmetry we can assume {${a {\geq}d}$} and {${b
{\geq}c}$}.
We show that {${f_{m}(a,b,c,d)}$} is
{${\Theta (m^{a+b-1})}$}
if either {${b>c}$} or {${a,b{\geq}1}$}. We also
show that {${f_{m}(0,b,b,0)}$} is {${\Theta (m^{b})}$} and {${f_{m}(a,0,0,d)}$}
is {${\Theta (m^{a})}$}. This can be viewed as a result
concerning
forbidden configurations and is further evidence for a conjecture of
Anstee
and Sali. Our key tool is a strong stability version of the Complete
Intersection
Theorem of Ahlswede and Khachatrian, which is of independent interest. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {17-20},
url = {http://www.dmtcs.org/proceedings/html/dmAE0104.abs.html}
}
@inproceedings{DMTCS-AE0105,
author = {David D{\'e}fossez},
title = {A sufficient condition for bicolorable hypergraphs},
keywords = {hypergraphs, coloring, Sterboul's conjecture},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { In this note we prove Sterboul's conjecture, that provides a
sufficient condition for the bicolorability of hypergraphs. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {21-24},
url = {http://www.dmtcs.org/proceedings/html/dmAE0105.abs.html}
}
@inproceedings{DMTCS-AE0106,
author = {Oleg Pikhurko and Joel Spencer and Oleg Verbitsky},
title = {Decomposable graphs and definitions with no quantifier alternation},
keywords = {descriptive complexity of graphs, first order logic, Ehrenfeucht game on graphs, graph decompositions},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Let {${D(G)}$} be the minimum quantifier depth of a first order
sentence
{${\Phi }$} that defines a graph {${G}$} up to
isomorphism
in terms of the adjacency and the equality relations. Let
{${D_{0}(G)}$}
be a variant of {${D(G)}$} where we do not allow quantifier
alternations
in {${\Phi }$}. Using large graphs decomposable in
complement-connected
components by a short sequence of serial and parallel decompositions,
we
show examples of {${G}$} on {${n}$} vertices with
{${D_{0}(G)\le 2\log ^{*}n+O(1)}$}. On the other hand, we prove a lower bound {${D_{0}(G)\ge \log ^{*}n-\log ^{*}\log ^{*}n-O(1)}$}
for all {${G}$}. Here {${\log ^{*}n}$} is equal
to
the minimum number of iterations of the binary logarithm needed to
bring {${n}$} below\ 1. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {25-30},
url = {http://www.dmtcs.org/proceedings/html/dmAE0106.abs.html}
}
@inproceedings{DMTCS-AE0107,
author = {Martin Kutz},
title = {Weak Positional Games on Hypergraphs},
keywords = { },
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { In a weak positional game, two players, Maker and Breaker, alternately
claim
vertices of a hypergraph until either Maker wins by getting a complete
edge
or all vertices are taken without this happening, a Breaker win. For
the
class of almost-disjoint hypergraphs of rank three (edges with up to
three
vertices only and edge-intersections on at most one vertex) we show
how
to find optimal strategies in polynomial time. Our result is based on
a
new type of decomposition theorem which might lead to a better
understanding of weak positional games in general. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {31-36},
url = {http://www.dmtcs.org/proceedings/html/dmAE0107.abs.html}
}
@inproceedings{DMTCS-AE0108,
author = {Christian Bey},
title = {Quadratic LYM inequalities},
keywords = {Sperner family, antichain, LYM inequality},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Let {${\mathcal{F}{\subseteq}2^{[n]}}$} be a
intersecting
Sperner family (i.e. {${A{\neg}{\subset}B}$}, {${A\cap B
{\neq}{\emptyset}}$}
for all {${A,B{\in}\mathcal{F}}$}) with profile
vector
{${(f_{i})_{i=0{\ldots}n}}$} (i.e.
{${f_{i}=|\mathcal{F}\cap \binom{[n]}{
i}|}$}). We present quadratic inequalities in the
{${f_{i}}$}'s
which sharpen the previously known linear LYM-type inequalities. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {37-40},
url = {http://www.dmtcs.org/proceedings/html/dmAE0108.abs.html}
}
@inproceedings{DMTCS-AE0109,
author = {Peter Bella and Daniel Kr{\'a}l' and Bojan Mohar and Katar\'{\i}na Quittnerov{\'a}},
title = {Labeling planar graphs with a condition at distance two },
keywords = {{${L(2,1)}$}-labeling, channel assignment problem, graph coloring, planar graphs},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { An {${L(2,1)}$}-labeling of a graph is a mapping
{${c:V(G){\rightarrow}\{0,{\ldots},K\}}$}
such that the labels assigned to neighboring vertices differ by at
least
{${2}$} and the labels of vertices at distance two are
different.
Griggs and Yeh [SIAM J. Discrete Math. 5 (1992), 586--595] conjectured
that
every graph {${G}$} with maximum degree {${\Delta }$}
has an {${L(2,1)}$}-labeling
with {${K{\leq}\Delta ^{2}}$}. We verify the
conjecture
for planar graphs with maximum degree {${\Delta {\neq}3}$}. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {41-44},
url = {http://www.dmtcs.org/proceedings/html/dmAE0109.abs.html}
}
@inproceedings{DMTCS-AE0110,
author = {Bruce Reed and David R.\ Wood},
title = {Fast separation in a graph with an excluded minor },
keywords = {graph algorithm, separator, minor},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Let {${G}$} be an {${n}$}-vertex {${m}$}-edge
graph with
weighted vertices. A pair of vertex sets {${A,B{\subseteq}V(G)}$} is
a
\emph{2/3-separation} of \emph{order} {${|A\cap B|}$} if
{${A \cup B
= V(G)}$}, there is no edge between {${A\ \\ B}$}
and
{${B\ \\ A}$}, and both {${A\ \\ B}$}
and
{${B\ \\ A}$} have weight at most {${2/3}$} the
total
weight of {${G}$}. Let {${{\ell}{\in}{\integers}+}$} be
fixed. Alon, Seymour
and Thomas [\emph{J.\ Amer.\ Math.\ Soc.}\ 1990]
presented an
algorithm that in {${\mathcal{O}(n^{1/2}m)}$}
time,
either outputs a {${K_{{\ell}}}$}-minor of
{${G}$}, or a separation of {${G}$}
of order {${\mathcal{O}(n^{1/2})}$}. Whether
there
is a {${\mathcal{O}(n+m)}$} time algorithm for this
theorem
was left as open problem. In this paper, we obtain a
{${\mathcal{O}(n+m)}$} time algorithm
at the expense of {${\mathcal{O}(n^{2/3})}$}
separator.
Moreover, our algorithm exhibits a tradeoff between running time and
the
order of the separator. In particular, for any given
{${\epsilon {\in}[0,1/2]}$},
our algorithm either outputs a {${K_{{\ell}}}$}-minor
of
{${G}$}, or a separation of {${G}$} with order
{${\mathcal{O}(n^{(2-\epsilon )/3})}$}
in {${\mathcal{O}(n^{1+\epsilon }+m)}$} time. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {45-50},
url = {http://www.dmtcs.org/proceedings/html/dmAE0110.abs.html}
}
@inproceedings{DMTCS-AE0111,
author = {Vladimir Deineko and Peter Jonsson and Mikael Klasson and Andrei Krokhin},
title = {Supermodularity on chains and complexity of maximum constraint satisfaction},
keywords = {maximum constraint satisfaction, complexity, supermodularity, Monge properties, digraph {${H}$}-colouring},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { In the maximum constraint satisfaction problem (Max CSP), one is given
a
finite collection of (possibly weighted) constraints on overlapping
sets
of variables, and the goal is to assign values from a given finite
domain
to the variables so as to maximise the number (or the total weight) of
satisfied
constraints. This problem is NP-hard in general so it is natural to
study
how restricting the allowed types of constraints affects the
complexity
of the problem. In this paper, we show that any Max CSP problem with a
finite
set of allowed constraint types, which includes all constants (i.e.
constraints
of the form {${x=a}$}), is either solvable in polynomial time
or
is NP-complete. Moreover, we present a simple description of all
polynomial-time
solvable cases of our problem. This description uses the well-known
combinatorial property of supermodularity. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {51-56},
url = {http://www.dmtcs.org/proceedings/html/dmAE0111.abs.html}
}
@inproceedings{DMTCS-AE0112,
author = {Dan Romik},
title = {Permutations with short monotone subsequences},
keywords = {Robinson-Schensted correspondence, Erd\H{o}s-Szekeres theorem, limit shape},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { We consider permutations of {${1,2,...,n^{2}}$} whose
longest
monotone subsequence is of length {${n}$} and are therefore
extremal
for the Erd\H{o}s-Szekeres\ Theorem. Such permutations
correspond
via the Robinson-Schensted correspondence to pairs of square {${n×
n}$}
Young tableaux. We show that all the bumping sequences are constant
and
therefore these permutations have a simple description in terms of the
pair
of square tableaux. We deduce a limit shape result for the plot of
values
of the typical such permutation, which in particular implies that the
first
value taken by such a permutation is with high probability
{${(1+o(1))n^{2}/2}$}. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {57-62},
url = {http://www.dmtcs.org/proceedings/html/dmAE0112.abs.html}
}
@inproceedings{DMTCS-AE0113,
author = {Tomasz Bartnicki and Jaros{\l}aw Grytczuk and Hal Kierstead},
title = {The game of arboricity},
keywords = { },
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Using a fixed set of colors {${C}$}, Ann and Ben color the
edges
of a graph {${G}$} so that no monochromatic cycle may appear.
Ann
wins if all edges of {${G}$} have been colored, while Ben wins
if
completing a coloring is not possible. The minimum size of
{${C}$}
for which Ann has a winning strategy is called the \emph{game
arboricity}
of {${G}$}, denoted by {${A_{g}(G)}$}. We prove
that
{${A_{g}(G) {\leq}3k}$} for any graph {${G}$}
of
arboricity {${k}$}, and that there are graphs such that
{${A_{g}(G){\geq}2k-2}$}.
The upper bound is achieved by a suitable version of the activation
strategy,
used earlier for the vertex coloring game. We also provide other
strategie based on induction. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {63-66},
url = {http://www.dmtcs.org/proceedings/html/dmAE0113.abs.html}
}
@inproceedings{DMTCS-AE0114,
author = {William Evans and Mohammad Ali Safari},
title = {Directed One-Trees },
keywords = {tree-width, tree-decomposition, d-width, d-decomposition, and haven order.},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { We identify the class of directed one-trees and prove the so-called
min-max
theorem for them. As a consequence, we establish the equality of
directed
tree-width and a new measure, d-width, on this class of graphs. In
addition,
we prove a property of all directed one-trees and use this property to
create
an {${O(n^{2})}$} recognition algorithm and an
{${O(n^{2})}$}
algorithm for solving the Hamiltonian cycle problem on directed
one-trees. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {67-72},
url = {http://www.dmtcs.org/proceedings/html/dmAE0114.abs.html}
}
@inproceedings{DMTCS-AE0115,
author = {Joshua Cooper and Benjamin Doerr and Joel Spencer and G{\'a}bor Tardos},
title = {Deterministic Random Walks on the Integers},
keywords = {random walks, chip firing games.},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { We analyze the one-dimensional version of Jim Propp's
{${P}$}-machine,
a simple deterministic process that simulates a random walk on
{${{\integers}}$}.
The ``output'' of the machine is astonishingly close to the expected
behavior
of a random walk, even on long intervals of space and time. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {73-76},
url = {http://www.dmtcs.org/proceedings/html/dmAE0115.abs.html}
}
@inproceedings{DMTCS-AE0116,
author = {John Talbot},
title = {Chromatic Tur{\'a}n problems and a new upper bound for the Tur{\'a}n density of {${K_{4}^{-}}$}},
keywords = {Extremal combinatorics, Tur{\'a}n-type problems, Hypergraphs},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { We consider a new type of extremal hypergraph problem: given an
{${r}$}-graph {${\mathcal{F}}$}
and an integer {${k{\geq}2}$} determine the maximum number of
edges in
an {${\mathcal{F}}$}-free, {${k}$}-colourable
{${r}$}-graph
on {${n}$} vertices. Our motivation for studying such problems
is
that it allows us to give a new upper bound for an old problem due to
Tur{\'a}n.
We show that a {${3}$}-graph in which any four vertices span at
most
two edges has density less than {${33\,/\,100}$},
improving
previous bounds of {${1\,/\,3}$} due to de Caen
[deC],
and {${1\,/\,3-4.5305{\times}10^{-6}}$} due to
Mubayi [M]. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {77-80},
url = {http://www.dmtcs.org/proceedings/html/dmAE0116.abs.html}
}
@inproceedings{DMTCS-AE0117,
author = {Daniel Gon\c{c}alves},
title = {On the {${L(p,1)}$}-labelling of graphs},
keywords = {lambda-labelling},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { In this paper we improve the best known bound for the
{${L(p,1)}$}-labelling of graphs with given maximal degree. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {81-86},
url = {http://www.dmtcs.org/proceedings/html/dmAE0117.abs.html}
}
@inproceedings{DMTCS-AE0118,
author = {Martin Charles Golumbic and Marina Lipshteyn and Michal Stern},
title = {Representations of Edge Intersection Graphs of Paths in a Tree},
keywords = {Paths of a tree, Intersection graphs, Weakly chordal graphs, Coloring, EPT-graphs},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Let {${\mathcal{P}}$} be a collection of nontrivial
simple
paths in a tree {${T}$}. The edge intersection graph of
{${\mathcal{P}}$},
denoted by {${EPT(\mathcal{P})}$}, has vertex set that
corresponds
to the members of {${\mathcal{P}}$}, and two vertices
are joined by an
edge if the corresponding members of {${\mathcal{P}}$}
share
a common edge in {${T}$}. An undirected graph {${G}$} is
called
an edge intersection graph of paths in a tree, if {${G}$} =
{${EPT(\mathcal{P})}$}
for some {${\mathcal{P}}$} and {${T}$}. The EPT
graphs
are useful in network applications. Scheduling undirected calls in a
tree
or assigning wavelengths to virtual connections in an optical tree
network
are equivalent to coloring its EPT graph. It is known that recognition
and
coloring of EPT graphs are NP-complete problems. However, the EPT
graphs
restricted to host trees of vertex degree 3 are precisely the chordal
EPT
graphs, and therefore can be colored in polynomial time complexity. We
prove
a new analogous result that weakly chordal EPT graphs are precisely
the
EPT graphs with host tree restricted to degree 4. This also implies
that
the coloring of the edge intersection graph of paths in a degree 4
tree
is polynomial. We raise a number of intriguing conjectures regarding
related families of graphs. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {87-92},
url = {http://www.dmtcs.org/proceedings/html/dmAE0118.abs.html}
}
@inproceedings{DMTCS-AE0119,
author = {Iliya Bouyukliev and Veerle Fack and Joost Winne},
title = {Hadamard matrices of order 36},
keywords = {Hadamard designs, double-even self-dual codes},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Before this work, at least 762 inequivalent Hadamard matrices of order
36
were known. We found 7238 Hadamard matrices of order 36 and 522
inequivalent
{${[72,36,12]}$} double-even self-dual codes which are obtained
from
all 2-{${(35,17,8)}$} designs with an automorphism of order 3
and 2 fixed points and blocks. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {93-98},
url = {http://www.dmtcs.org/proceedings/html/dmAE0119.abs.html}
}
@inproceedings{DMTCS-AE0120,
author = {Louis Esperet and Micka{\"e}l Montassier and Andr{\'e} Raspaud},
title = {Linear choosability of graphs},
keywords = {vertex-coloring, list, acyclic, 3-frugal, choosability under constraints.},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { A proper vertex coloring of a non oriented graph {${G=(V,E)}$}
is
\emph{linear} if the graph induced by the vertices of two color
classes
is a forest of paths. A graph {${G}$} is {${L}$}-list
colorable
if for a given list assignment {${L=\{L(v):
v{\in}V\}}$},
there exists a proper coloring {${c}$} of {${G}$} such
that
{${c(v){\in}L(v)}$} for all {${v{\in}V}$}. If
{${G}$}
is {${L}$}-list colorable for every list assignment with
{${|L(v)|{\geq}k}$}
for all {${v{\in}V}$}, then {${G}$} is said
{${k}$}-choosable.
A graph is said to be lineary {${k}$}-choosable if the coloring
obtained
is linear. In this paper, we investigate the linear choosability of
graphs
for some families of graphs: graphs with small maximum degree, with
given
maximum average degree, planar graphs... Moreover, we prove that
determining
whether a bipartite subcubic planar graph is lineary 3-colorable is an
NP-complete problem. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {99-104},
url = {http://www.dmtcs.org/proceedings/html/dmAE0120.abs.html}
}
@inproceedings{DMTCS-AE0121,
author = {Michael J. Pelsmajer and Marcus Schaefer and Daniel \v{S}tefankovi\v{c}},
title = {Removing Even Crossings},
keywords = {Hanani's theorem, Tutte's theorem, even crossings, crossing number, odd crossing number, independent odd crossing number},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { An edge in a drawing of a graph is called \emph{even} if it
intersects
every other edge of the graph an even number of times. Pach and
T{\'o}th
proved that a graph can always be redrawn such that its even edges are
not
involved in any intersections. We give a new, and significantly
simpler,
proof of a slightly stronger statement. We show two applications of
this
strengthened result: an easy proof of a theorem of Hanani and Tutte
(not
using Kuratowski's theorem), and the result that the odd crossing
number
of a graph equals the crossing number of the graph for values of at
most
{${3}$}. We begin with a disarmingly simple proof of a weak
(but
standard) version of the theorem by Hanani and Tutte. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {105-110},
url = {http://www.dmtcs.org/proceedings/html/dmAE0121.abs.html}
}
@inproceedings{DMTCS-AE0122,
author = {Christian Deppe and Holger Schnettler},
title = {On the {${3/4}$}-Conjecture for Fix-Free Codes},
keywords = {Fix-free Codes, Kraft inequality, {${3/4}$}-Conjecture},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { In this paper we concern ourself with the question, whether there
exists
a fix-free code for a given sequence of codeword lengths. We focus
mostly
on results which shows the {${3\,/\,4}$}-conjecture
for special kinds of lengths sequences. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {111-116},
url = {http://www.dmtcs.org/proceedings/html/dmAE0122.abs.html}
}
@inproceedings{DMTCS-AE0123,
author = {Richard Anstee and Balin Fleming and Zolt{\'a}n F{\"u}redi and Attila Sali},
title = {Color critical hypergraphs and forbidden configurations},
keywords = {forbidden configuration, color critical hypergraph, linear algebra method},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { The present paper connects sharpenings of Sauer's bound on forbidden
configurations
with color critical hypergraphs. We define a matrix to be
\emph{simple}
if it is a (0,1)-matrix with no repeated columns. Let {${F}$}
be
a {${k× l}$} (0,1)-matrix (the forbidden configuration). Assume
{${A}$}
is an {${m× n}$} simple matrix which has no submatrix which is
a
row and column permutation of {${F}$}. We define
{${\textrm{forb}(m,F)}$}
as the best possible upper bound on {${n}$}, for such a matrix
{${A}$},
which depends on {${m}$} and {${F}$}. It is known that
{${\textrm{forb}(m,F)=O(m^{k})}$}
for any {${F}$}, and Sauer's bond states that
{${\textrm{forb}(m,F)=O(m^{k-1})}$}
fore \emph{simple} {${F}$}. We give sufficient condition for
non-simple
{${F}$} to have the same bound using linear algebra methods to
prove
a generalization of a result of Lovász on color critical hypergraphs. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {117-122},
url = {http://www.dmtcs.org/proceedings/html/dmAE0123.abs.html}
}
@inproceedings{DMTCS-AE0124,
author = {Drago Bokal and Ga\v{s}per Fijav\v{z} and Bojan Mohar},
title = {Minor-monotone crossing number},
keywords = {crossing number, graph minor, minor-monotone graph parameter},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { The minor crossing number of a graph {${G}$},
{${\textrm{mcr}(G)}$},
is defined as the minimum crossing number of all graphs that contain
{${G}$}
as a minor. We present some basic properties of this new
minor-monotone graph
invariant. We give estimates on {${\textrm{mcr}}$} for
some
important graph families using the topological structure of graphs
satisfying {${\textrm{mcr}(G) {\leq}k}$}. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {123-128},
url = {http://www.dmtcs.org/proceedings/html/dmAE0124.abs.html}
}
@inproceedings{DMTCS-AE0125,
author = {Veerle Fack and Svetlana Topalova and Joost Winne},
title = {On the enumeration of uniquely reducible double designs},
keywords = {double design, projective plane, enumeration},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { A double 2-({${v}$},{${k}$},{${2\lambda }$})
design is a design which is reducible
into two 2-({${v}$},{${k}$},{${\lambda }$})
designs.
It is called uniquely reducible if it has, up to equivalence, only one
reduction.
We present properties of uniquely reducible double designs which show
that
their total number can be determined if only the designs with
non-trivial
automorphisms are classified with respect to their automorphism group.
As
an application, after proving that a reducible 2-(21,5,2) design is
uniquely
reducible, we establish that the number of all reducible 2-(21,5,2)
designs is 1 746 461 307. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {129-132},
url = {http://www.dmtcs.org/proceedings/html/dmAE0125.abs.html}
}
@inproceedings{DMTCS-AE0126,
author = {Noga Alon and Jaros{\l}aw Grytczuk},
title = {Nonrepetitive colorings of graphs},
keywords = { },
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = {A vertex coloring of a graph {${G}$} is {${k}$}\emph{-nonrepetitive} if
one
cannot find a periodic sequence with {${k}$} blocks on any
simple
path of {${G}$}. The minimum number of colors needed for such
coloring
is denoted by {${\pi _{k}(G)}$} . This idea combines
graph
colorings with Thue sequences introduced at the beginning of 20th
century.
In particular Thue proved that if {${G}$} is a simple path of
any
length greater than 4 then {${\pi _{2}(G)=3}$} and
{${\pi _{3}(G)=2}$}.
We investigate {${\pi _{k}(G)}$} for other classes of
graphs.
Particularly interesting open problem is to decide if there is,
possibly
huge, {${k}$} such that {${\pi _{k}(G)}$} is
bounded for planar graphs. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {133-134},
url = {http://www.dmtcs.org/proceedings/html/dmAE0126.abs.html}
}
@inproceedings{DMTCS-AE0127,
author = {Paul Bonsma},
title = {A characterization of extremal graphs with no matching-cut},
keywords = {matching-cut, matching immune, extremal graphs},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { A graph is called (matching-)immune if it has no edge cut that is also
a
matching. Farley and Proskurowski proved that for all immune graphs
{${G=(V,E)}$},
{${|E|{\geq}\lceil 3(|V|-1)/2\rceil }$}, and constructed a
large
class of immune graphs that attain this lower bound for every value of
{${|V(G)|}$},
called ABC graphs. They conjectured that every immune graph that
attains
this lower bound is an ABC graph. We present a proof of this
conjecture. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {135-138},
url = {http://www.dmtcs.org/proceedings/html/dmAE0127.abs.html}
}
@inproceedings{DMTCS-AE0128,
author = {Gyula Pap},
title = {Packing non-returning {${A}$}-paths algorithmically},
keywords = {{${A}$}-paths, matching},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { In this paper we present an algorithmic approach to packing
{${A}$}-paths.
It is regarded as a generalization of Edmonds' matching algorithm,
however
there is the significant difference that here we do not build up any
kind
of alternating tree. Instead we use the so-called 3-way lemma, which
either
provides augmentation, or a dual, or a subgraph which can be used for
contraction.
The method works in the general setting of packing non-returning
{${A}$}-paths.
It also implies an ear-decomposition of criticals, as a generalization
of
the odd ear-decomposition of factor-critical graph. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {139-144},
url = {http://www.dmtcs.org/proceedings/html/dmAE0128.abs.html}
}
@inproceedings{DMTCS-AE0129,
author = {{\'E}ric R{\'e}mila},
title = {Structure of spaces of rhombus tilings in the lexicograhic case},
keywords = {rhombus tiling, flip, connectivity},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Rhombus tilings are tilings of zonotopes with rhombohedra. We study a
class
of \emph{lexicographic} rhombus tilings of zonotopes, which are
deduced
from higher Bruhat orders relaxing the unitarity condition. Precisely,
we
fix a sequence {${(v_{1}, v_{2},{\ldots},
v_{D})}$}
of vectors of {${{\reals}^{d}}$} and a sequence
{${(m_{1},
m_{2},{\ldots}, m_{D})}$} of positive integers. We
assume
(lexicographic hypothesis) that for each subsequence
{${(v_{i_{1}},
v_{i_{2}},{\ldots}, v_{i_{d}})}$}
of
length {${d}$}, we have {${det(v_{i_{1}},
v_{i_{2}},{\ldots},
v_{i_{d}}) > 0}$}. The zonotope {${Z}$}
is
the set {${\{ \sum\alpha _{i}v_{i} \ 0
{\leq}\alpha _{i}
{\leq}m_{i} \}}$}. Each prototile used in a tiling
of
{${Z}$} is a rhombohedron constructed from a subsequence of
{${d}$}
vectors. We prove that the space of tilings of {${Z}$} is a
graded poset, with minimal and maximal element. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {145-150},
url = {http://www.dmtcs.org/proceedings/html/dmAE0129.abs.html}
}
@inproceedings{DMTCS-AE0130,
author = {Andrew D. King and Bruce A. Reed and Adrian R. Vetta},
title = {An upper bound for the chromatic number of line graphs},
keywords = { },
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = {It was conjectured by Reed [reed98conjecture] that for any graph
{${G}$},
the graph's chromatic number {${\chi (G)}$} is bounded above by
{${\lceil \Delta (G)
+1 + \omega (G)\,/\,2\rceil }$}, where
{${\Delta (G)}$}
and {${\omega (G)}$} are the maximum degree and clique number
of
{${G}$}, respectively. In this paper we prove that this bound
holds
if {${G}$} is the line graph of a multigraph. The proof yields
a
polynomial time algorithm that takes a line graph {${G}$} and
produces a colouring that achieves our bound. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {151-156},
url = {http://www.dmtcs.org/proceedings/html/dmAE0130.abs.html}
}
@inproceedings{DMTCS-AE0131,
author = {Mat\v{e}j Stehl\'{\i}k},
title = {Connected {${\tau }$}-critical hypergraphs of minimal size},
keywords = {{${\tau }$}-critical hypergraph, {${\chi }$}-critical {${3}$}-chromatic hypergraph},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = {A hypergraph {${\mathcal{H}}$} is {${\tau }$}-critical if
{${\tau (\mathcal{H}-E)
< \tau (\mathcal{H})}$} for every edge {${E
{\in}\mathcal{H}}$},
where {${\tau (\mathcal{H})}$} denotes the transversal
number
of {${\mathcal{H}}$}. It can be shown that a connected
{${\tau }$}-critical
hypergraph {${\mathcal{H}}$} has at least
{${2\tau (\mathcal{H})-1}$}
edges; this generalises a classical theorem of Gallai on
{${\chi }$}-vertex-critical
graphs with connected complements. In this paper we study connected
{${\tau }$}-critical
hypergraphs {${\mathcal{H}}$} with exactly
{${2\tau (\mathcal{H})-1}$}
edges. We prove that such hypergraphs have at least
{${2\tau (\mathcal{H})-1}$} vertices, and
characterise those with {${2\tau (\mathcal{H})-1}$}
vertices
using a directed odd ear decomposition of an associated digraph. Using
Seymour's characterisation
of {${\chi }$}-critical {${3}$}-chromatic square
hypergraphs, we also show
that a connected square hypergraph {${\mathcal{H}}$}
with
fewer than {${2\tau (\mathcal{H})}$} edges is
{${\tau }$}-critical if and
only if it is {${\chi }$}-critical {${3}$}-chromatic.
Finally,
we deduce some new results on {${\chi }$}-vertex-critical
graphs with connected complements. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {157-160},
url = {http://www.dmtcs.org/proceedings/html/dmAE0131.abs.html}
}
@inproceedings{DMTCS-AE0132,
author = {Francisco Javier Zaragoza Mart\'{\i}nez},
title = {The Windy Postman Problem on Series-Parallel Graphs},
keywords = {windy postman problem, series-parallel graphs, integral polyhedra},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { The \emph{windy postman problem} is the NP-hard problem of finding
the
minimum cost of a tour traversing all edges of an undirected graph,
where
the cost of traversal of an edge depends on the direction. Given an
undirected
graph {${G}$}, we consider the polyhedron {${O(G)}$}
induced
by the linear programming relaxation of a well-known integer
programming
formulation of the problem. We say that {${G}$} is \emph{windy
postman
perfect} if {${O(G)}$} is integral. There exists a
polynomial-time
algorithm, based on the ellipsoid method, to solve the windy postman
problem
for the class of windy postman perfect graphs. Eulerian graphs and
trees
are windy postman perfect. By considering a family of polyhedra
related
to {${O(G)}$}, we prove that series-parallel graphs are windy
postman
perfect, therefore solving a conjecture of\ [Win1987a]. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {161-166},
url = {http://www.dmtcs.org/proceedings/html/dmAE0132.abs.html}
}
@inproceedings{DMTCS-AE0133,
author = {Gohar Kyureghyan},
title = {Crooked Maps in Finite Fields},
keywords = {almost perfect maps, Gold power function, quadrics},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = {We consider the maps {${f:\mathbb{F}_{2^{n}}
{\rightarrow}\mathbb{F}_{2^{n}}}$}
with the property that the set {${\{ f(x+a)+ f(x): x
{\in}F_{2^{n}}\}
}$} is a hyperplane or a complement of hyperplane for every
{${a
{\in}\mathbb{F}_{2^{n}}^{*}}$}.
The
main goal of the talk is to show that almost all maps {${f(x) =
\sum_{b
{\in}B}c_{b}(x+b)^{d}}$}, where {${B
{\subset}\mathbb{F}_{2^{n}}}$}
and {${\sum_{b {\in}B}c_{b} {\neq}0}$},
are
not of that type. In particular, the only such power maps have
exponents
{${2^{i}+2^{j}}$} with gcd{${(n,
i-j)=1}$}.
We give also a geometrical characterization of this maps. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {167-170},
url = {http://www.dmtcs.org/proceedings/html/dmAE0133.abs.html}
}
@inproceedings{DMTCS-AE0134,
author = {Javier Barajas and Oriol Serra},
title = {Distance graphs with maximum chromatic number},
keywords = {Distance graphs, chromatic number},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Let {${D}$} be a finite set of integers. The distance graph
{${G(D)}$}
has the set of integers as vertices and two vertices at distance
{${d
{\in}D}$} are adjacent in {${G(D)}$}. A conjecture of
Xuding
Zhu states that if the chromatic number of {${G (D)}$} achieves
its
maximum value {${|D|+1}$} then the graph has a clique of order
{${|D|}$}.
We prove that the chromatic number of a distance graph with
{${D=\{
a,b,c,d\}}$} is five if and only if either {${D=\{
1,2,3,4k\}}$}
or {${D=\{ a,b,a+b,a+2b\}}$} with {${a \equiv 0
\textrm{
mod } 2}$} and {${b \equiv 1 \textrm{ mod }
2}$}.
This confirms Zhu's conjecture for {${|D|=4}$}. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {171-174},
url = {http://www.dmtcs.org/proceedings/html/dmAE0134.abs.html}
}
@inproceedings{DMTCS-AE0135,
author = {M{\'a}rton Makai},
title = {Matroid matching with Dilworth truncation},
keywords = {matroid matching, Dilworth truncation, double circuit property},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Let {${H=(V,E)}$} be a hypergraph and let {${k\ge 1}$}
and {${l\ge 0}$}
be fixed integers. Let {${\mathcal{M}}$} be the
matroid
with ground-set {${E}$} s.t.\ a set {${F{\subseteq}E}$}
is
independent if and only if each {${X{\subseteq}V}$} with
{${k|X|-l\ge 0}$}
spans at most {${k|X|-l}$} hyperedges of {${F}$}. We
prove that if
{${H}$} is dense enough, then {${\mathcal{M}}$}
satisfies
the double circuit property, thus the min-max formula of Dress and
Lov{\'a}sz on the
maximum matroid matching holds for {${\mathcal{M}}$}.
Our
result implies the Berge-Tutte formula on the maximum matching of
graphs
({${k=1}$}, {${l=0}$}), generalizes Lov{\'a}sz'
graphic
matroid (cycle matroid) matching formula to hypergraphs
({${k=l=1}$})
and gives a min-max formula for the maximum matroid matching in the
2-dimensional
rigidity matroid ({${k=2}$}, {${l=3}$}). },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {175-180},
url = {http://www.dmtcs.org/proceedings/html/dmAE0135.abs.html}
}
@inproceedings{DMTCS-AE0136,
author = {Audrey Lee and Ileana Streinu},
title = {Pebble Game Algorithms and {${(k,l)}$}-Sparse Graphs},
keywords = {sparse graph, pebble game, rigidity, arboricity, graph orientation with bounded degree},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { A multi-graph {${G}$} on {${n}$} vertices is
{${(k,l)}$}-sparse
if every subset of {${n'{\leq}n}$} vertices spans at most
{${kn'-l}$}
edges, {${0 {\leq}l < 2k}$}. {${G}$} is
\emph{tight}
if, in addition, it has exactly {${kn - l}$} edges. We
characterize
{${(k,l)}$}-sparse graphs via a family of simple, elegant and
efficient
algorithms called the {${(k,l)}$}-pebble games. As
applications,
we use the pebble games for computing \emph{components} (maximal
tight
subgraphs) in sparse graphs, to obtain inductive (Henneberg)
constructions,
and, when {${l=k}$}, edge-disjoint tree decompositions. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {181-186},
url = {http://www.dmtcs.org/proceedings/html/dmAE0136.abs.html}
}
@inproceedings{DMTCS-AE0137,
author = {Tamon Stephen},
title = {On the Grone-Merris conjecture},
keywords = {graph Laplacian, majorization, graph spectrum, degree sequence},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Grone and Merris [GM94] conjectured that the Laplacian spectrum of a
graph
is majorized by its conjugate vertex degree sequence. We prove that
this
conjecture holds for a class of graphs including trees. We also show
that
this conjecture and its generalization to graphs with Dirichlet
boundary conditions are equivalent. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {187-192},
url = {http://www.dmtcs.org/proceedings/html/dmAE0137.abs.html}
}
@inproceedings{DMTCS-AE0138,
author = {Ross J. Kang and Tobias M{\"u}ller and Jean-S{\'e}bastien Sereni},
title = {Improper colouring of (random) unit disk graphs},
keywords = {improper colouring, unit disk graphs, random unit disk graphs, radio channel assignment},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { For any graph {${G}$}, the {${k}$}-\emph{improper
chromatic
number} {${\chi ^{k}(G)}$} is the smallest number
of
colours used in a colouring of {${G}$} such that each colour
class
induces a subgraph of maximum degree {${k}$}. We investigate
the
ratio of the {${k}$}-improper chromatic number to the clique
number
for unit disk graphs and random unit disk graphs to extend results
of\ [McRe99,
McD03] (where they considered only proper colouring). },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {193-198},
url = {http://www.dmtcs.org/proceedings/html/dmAE0138.abs.html}
}
@inproceedings{DMTCS-AE0139,
author = {Daniela K{\"u}hn and Deryk Osthus},
title = {{${K_{{\ell}}^{-}}$}-factors in graphs},
keywords = {graph packing, factor, critical chromatic number},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Let {${K_{{\ell}}^{-}}$} denote the graph
obtained
from {${K_{{\ell}}}$} by deleting one edge. We show
that
for every {${\gamma >0}$} and every integer
{${{\ell}{\geq}4}$} there exists
an integer {${n_{0}=n_{0}(\gamma ,{\ell})}$}
such that every
graph {${G}$} whose order {${n{\geq}n_{0}}$}
is
divisible by {${{\ell}}$} and whose minimum degree is at
least {${({\ell}^{2}-3{\ell}+1\,/\,{\ell}({\ell}-2)+\gamma )n}$}
contains a {${K_{{\ell}}^{-}}$}-factor,
i.e.\ a collection
of disjoint copies of {${K_{{\ell}}^{-}}$}
which
covers all vertices of\ {${G}$}. This is best possible up
to
the error term {${\gamma n}$} and yields an approximate
solution to a conjecture of Kawarabayashi. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {199-202},
url = {http://www.dmtcs.org/proceedings/html/dmAE0139.abs.html}
}
@inproceedings{DMTCS-AE0140,
author = {Kathie Cameron and Jack Edmonds},
title = {Finding a Strong Stable Set or a Meyniel Obstruction in any Graph},
keywords = {stable set, independent set, graph colouring, Meyniel graph, perfect graph},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { A strong stable set in a graph {${G}$} is a stable set that
contains
a vertex of every maximal clique of {${G}$}. A Meyniel
obstruction
is an odd circuit with at least five vertices and at most one chord.
Given
a graph {${G}$} and a vertex {${v}$} of {${G}$},
we
give a polytime algorithm to find either a strong stable set
containing
{${v}$} or a Meyniel obstruction in {${G}$}. This can
then
be used to find in any graph, a clique and colouring of the same size
or a Meyniel obstruction. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {203-206},
url = {http://www.dmtcs.org/proceedings/html/dmAE0140.abs.html}
}
@inproceedings{DMTCS-AE0141,
author = {Kenji Kashiwabara and Masataka Nakamura},
title = {NBC Complexes of Convex Geometries},
keywords = {broken circuit, characteristic polynomial, NBC basis theorem},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { We introduce a notion of a \emph{broken circuit} and an \emph{NBC
complex}
for an (abstract) convex geometry. Based on these definitions, we
shall
show the analogues of the Whitney-Rota's formula and Brylawski's
decomposition
theorem for broken circuit complexes on matroids for convex
geometries.
We also present an Orlik-Solomon type algebra on a convex geometry,
and
show the NBC generating theorem. This note is on the same line as the
studies in [nakamura03a, okamoto-nakamura, nakamura]. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {207-212},
url = {http://www.dmtcs.org/proceedings/html/dmAE0141.abs.html}
}
@inproceedings{DMTCS-AE0142,
author = {Adrian Kosowski and Micha{\l} Ma{\l}afiejski and Pawe{\l} {\.Z}yli{\'n}ski},
title = {Packing Three-Vertex Paths in a Subcubic Graph},
keywords = {three-vertex paths, subcubic graphs, path packing},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { In our paper we consider the {${P_{3}}$}-packing
problem
in subcubic graphs of different connectivity, improving earlier
results
of Kelmans and Mubayi [KM04]. We show that there exists a
{${P_{3}}$}-packing
of at least {${\lceil 3n/4\rceil }$} vertices in any connected
subcubic
graph of order {${n>5}$} and minimum vertex degree
{${\delta {\geq}2}$},
and that this bound is tight. The proof is constructive and implied by
a
linear-time algorithm. We use this result to show that any
{${2}$}-connected cubic graph
of order {${n>8}$} has a {${P_{3}}$}-packing
of
at least {${\lceil 7n/9 \rceil }$} vertices. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {213-218},
url = {http://www.dmtcs.org/proceedings/html/dmAE0142.abs.html}
}
@inproceedings{DMTCS-AE0143,
author = {Anna Llad{\'o}},
title = {Largest cliques in connected supermagic graphs},
keywords = {Labelings of graphs, magic graphs, Sidon sets.},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { A graph {${G=(V,E)}$} is said to be \emph{magic} if there
exists
an integer labeling {${f: V\cup E {\rightarrow}[1, |V\cup E|]}$} such
that
{${f(x)+f(y)+f(xy)}$} is constant for all edges
{${xy{\in}E}$}.
Enomoto, Masuda and Nakamigawa proved that there are magic graphs of
order
at most {${3n^{2}+o(n^{2})}$} which contain a
complete
graph of order {${n}$}. Bounds on Sidon sets show that the
order of
such a graph is at least {${n^{2}+o(n^{2})}$}.
We
close the gap between those two bounds by showing that, for any given
graph
{${H}$} of order {${n}$}, there are connected magic
graphs
of order {${n^{2}+o(n^{2})}$} containing
{${H}$}
as an induced subgraph. Moreover it can be required that the graph
admits
a supermagic labelling {${f}$}, which satisfies the additional
condition {${f(V)=[1,|V|]}$}. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {219-222},
url = {http://www.dmtcs.org/proceedings/html/dmAE0143.abs.html}
}
@inproceedings{DMTCS-AE0144,
author = {Anthony Bonato and Jeannette Janssen},
title = {Infinite limits and folding},
keywords = {massive networks, duplication model, infinite random graph, folding, adjacency property, graph homomorphism},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { We study infinite limits of graphs generated by the duplication model
for
biological networks. We prove that with probability {${1}$},
the
sole nontrivial connected component of the limits is unique up to
isomorphism.
We describe certain infinite deterministic graphs which arise
naturally
from the model. We characterize the isomorphism type and induced
subgraph
structure of these infinite graphs using the notion of dismantlability
from
the theory of vertex pursuit games, and graph homomorphisms. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {223-228},
url = {http://www.dmtcs.org/proceedings/html/dmAE0144.abs.html}
}
@inproceedings{DMTCS-AE0145,
author = {Gyula O.H. Katona},
title = {Excluded subposets in the Boolean lattice},
keywords = {extremal problems, families of subsets},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { We are looking for the maximum number of subsets of an
{${n}$}-element
set not containing {${4}$} distinct subsets satisfying {${A
{\subset}B,
C {\subset}B, C {\subset}D}$}. It is proved that this number is at least
the
number of the {${\lfloor n\,/\,2\rfloor }$}-element
sets
times {${1+2\,/\,n}$}, on the other hand an upper
bound
is given with {${4}$} replaced by the value {${2}$}. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {229-230},
url = {http://www.dmtcs.org/proceedings/html/dmAE0145.abs.html}
}
@inproceedings{DMTCS-AE0146,
author = {Miri Priesler and Michael Tarsi},
title = {Multigraph decomposition into multigraphs with two underlying edges},
keywords = {Decomposition, Multigraph, NPC},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Due to some intractability considerations, reasonable formulation of
necessary
and sufficient conditions for decomposability of a general multigraph
{${G}$}
into a fixed connected multigraph {${H}$}, is probably not
feasible
if the underlying simple graph of {${H}$} has three or more
edges.
We study the case where {${H}$} consists of two underlying
edges.
We present necessary and sufficient conditions for
{${H}$}-decomposability
of {${G}$}, which hold when certain size parameters of
{${G}$}
lies within some bounds which depends on the multiplicities of the two
edges
of {${H}$}. We also show this result to be "tight" in the sense
that
even a slight deviation of these size parameters from the given bounds
results
intractability of the corresponding decision problem. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {231-234},
url = {http://www.dmtcs.org/proceedings/html/dmAE0146.abs.html}
}
@inproceedings{DMTCS-AE0147,
author = {Frank G{\"o}ring},
title = {Mader Tools},
keywords = {graph, {${H}$}-path, separator},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { The deep theorem of Mader concerning the number of internally disjoint
{${H}$}-paths
is a very powerfull tool. Nevertheless its use is very difficult,
because
one has to deal with a very reach family of separators. This paper
shows
several ways to strengthen Mader's theorem by certain additional
restrictions of the appearing separators. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {235-238},
url = {http://www.dmtcs.org/proceedings/html/dmAE0147.abs.html}
}
@inproceedings{DMTCS-AE0148,
author = {Zoran Nikoloski\ and Narsingh Deo and Ludek Kucera},
title = {Degree-correlation of Scale-free graphs},
keywords = {degree-correlation, scale-free degree distribution, linearized chord diagrams},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Barab{\'a}si and Albert [1] suggested modeling scale-free networks
by
the following random graph process: one node is added at a time and is
connected
to an earlier node chosen with probability proportional to its degree.
A
recent empirical study of Newman [5] demonstrates existence of
degree-correlation
between degrees of adjacent nodes in real-world networks. Here we
define
the \textit{degree correlation}---correlation of the degrees in a pair
of
adjacent nodes---for a random graph process. We determine
asymptotically
the joint probability distribution for node-degrees, {${d}$}
and
{${d'}$}, of adjacent nodes for every {${0{\leq}d{\leq}
d'{\leq}n^{1\,/\,5}}$},
and use this result to show that the model of Barab{\'a}si and
Albert
does not generate degree-correlation. Our theorem confirms the result
in
[KR01], obtained by using the mean-field heuristic approach. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {239-244},
url = {http://www.dmtcs.org/proceedings/html/dmAE0148.abs.html}
}
@inproceedings{DMTCS-AE0149,
author = {Jaroslav Ne\v{s}et\v{r}il and Yared Nigussie},
title = {Density of universal classes of series-parallel graphs},
keywords = {circular chromatic number, homomorphism, series-parallel graphs, universality},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { A class of graphs {${\mathcal{C}}$} ordered by the
homomorphism
relation is \emph{universal} if every countable partial order can be
embedded
in {${\mathcal{C}}$}. It was shown in [ZH] that the
class {${\mathcal{C}_{k}}$} of {${k}$}-colorable
graphs, for any fixed {${k{\geq}3}$}, induces a universal
partial order. In [HN1], a surprisingly
small subclass of {${\mathcal{C}_{3}}$} which
is
a proper subclass of {${K_{4}}$}-minor-free graphs
({${\mathcal{G}/K_{4}}$})
is shown to be universal. In another direction, a density result was
given in [PZ], that for
each rational number {${a/b {\in}[2,8/3]\cup \{3\}}$},
there
is a {${K_{4}}$}-minor-free graph with circular
chromatic
number equal to {${a/b}$}. In this note we show for each
rational
number {${a/b}$} within this interval the class {${{\mathcal{K}}_{a/b}}$}
of {${K_{4}}$}-minor-free graphs with circular
chromatic
number {${a/b}$} is universal if and only if {${a/b
{\neq}2}$},
{${5/2}$} or {${3}$}. This shows yet another surprising
richness
of the {${K_{4}}$}-minor-free class that it contains
universal classes as dense as the rational numbers. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {245-250},
url = {http://www.dmtcs.org/proceedings/html/dmAE0149.abs.html}
}
@inproceedings{DMTCS-AE0150,
author = {Gordana Mani{\'c} and Yoshiko Wakabayashi},
title = {Packing triangles in low degree graphs and indifference graphs},
keywords = {triangle packing, approximation algorithm, polynomial algorithm, low degree graph, indifference graph},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { We consider the problems of finding the maximum number of
vertex-disjoint
triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph.
Both
problems are NP-hard. The algorithm with the best approximation
guarantee
known so far for these problems has ratio {${3/2 + {\varepsilon}}$}, a
result
that follows from a more general algorithm for set packing obtained by
Hurkens
and Schrijver in 1989. We present improvements on the approximation
ratio
for restricted cases of {${VTP}$} and {${ETP}$} that are
known
to be APX-hard: we give an approximation algorithm for
{${VTP}$}
on graphs with maximum degree {${4}$} with ratio slightly less
than
{${1.2}$}, and for {${ETP}$} on graphs with maximum
degree
{${5}$} with ratio {${4/3}$}. We also present an exact
linear-time
algorithm for {${VTP}$} on the class of indifference graphs. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {251-256},
url = {http://www.dmtcs.org/proceedings/html/dmAE0150.abs.html}
}
@inproceedings{DMTCS-AE0151,
author = {Hortensia Galeana-S{\'a}nchez and Mucuy-Kak Guevara},
title = {Semikernels modulo F in Digraphs},
keywords = {kernel, semikernel, semikernel modulo F, kernel perfect digraph, critical kernel imperfect digraph},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { A kernel {${N}$} of a digraph {${D}$} is an independent
set of vertices
of {${D}$} such that for every {${w{\in}V(D)-N}$} there
exists
an arc from {${w}$} to {${N}$}. If every induced
subdigraph
of {${D}$} has a kernel, {${D}$} is said to be a kernel
perfect
digraph. Minimal non-kernel perfect digraph are called critical kernel
imperfect
digraph. If {${F}$} is a set of arcs of {${D}$}, a
semikernel
modulo {${F}$}, {${S}$} of {${D}$} is an
independent
set of vertices of {${D}$} such that for every
{${z{\in}V(D)-
S}$} for which there exists an {${Sz-}$}arc of
{${D-F}$},
there also exists an {${zS-}$}arc in {${D}$}. In this
talk
some structural results concerning critical kernel imperfect and
sufficient
conditions for a digraph to be a critical kernel imperfect digraph are
presented. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {257-262},
url = {http://www.dmtcs.org/proceedings/html/dmAE0151.abs.html}
}
@inproceedings{DMTCS-AE0152,
author = {Ross M. Richardson and Van H. Vu and Lei Wu},
title = {Random Inscribing Polytopes},
keywords = {random polytope, inscribing, boundary, volume, variance, central limit theorem},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = {For convex bodies {${K}$} with {${\mathcal{C}^{2}}$}
boundary
in {${{\reals}^{d}}$}, we provide results on the volume
of
random polytopes with vertices chosen along the boundary of
{${K}$}
which we call \emph{random inscribing polytopes}. In particular, we
prove
results concerning the variance and higher moments of the volume, as
well
as show that the random inscribing polytopes generated by the Poisson
process satisfy central limit theorem. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {263-266},
url = {http://www.dmtcs.org/proceedings/html/dmAE0152.abs.html}
}
@inproceedings{DMTCS-AE0153,
author = {Dmitri G. Fon-Der-Flaass and Anna E. Frid},
title = {On infinite permutations},
keywords = {infinite permutation, ordering, periodicity, complexity, subword complexity, Sturmian words},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { We define an infinite permutation as a sequence of reals taken up to
the
order, or, equivalently, as a linear ordering of a finite or countable
set.
Then we introduce and characterize periodic permutations;
surprisingly,
for each period {${t}$} there is an infinite number of distinct
{${t}$}-periodic
permutations. At last, we introduce a complexity notion for
permutations
analogous to subword complexity for words, and consider the problem of
minimal
complexity of non-periodic permutations. Its answer is different for
the right infinite and the bi-infinite case. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {267-272},
url = {http://www.dmtcs.org/proceedings/html/dmAE0153.abs.html}
}
@inproceedings{DMTCS-AE0154,
author = {Daniela K{\"u}hn and Deryk Osthus},
title = {Matchings and Hamilton cycles in hypergraphs},
keywords = {matchings, Hamilton cycles, packings, uniform hypergraphs},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { It is well known that every bipartite graph with vertex classes of
size
{${n}$} whose minimum degree is at least {${n/2}$}
contains
a perfect matching. We prove an analogue of this result for uniform
hypergraphs.
We also provide an analogue of Dirac's theorem on Hamilton cycles for
{${3}$}-uniform
hypergraphs: We say that a {${3}$}-uniform hypergraph has a
Hamilton
cycle if there is a cyclic ordering of its vertices such that every
pair
of consecutive vertices lies in a hyperedge which consists of three
consecutive
vertices. We prove that for every {${\epsilon > 0}$} there
is
an {${n_{0}}$} such that every {${3}$}-uniform
hypergraph
of order {${n {\geq}n_{0}}$} whose minimum degree is
at
least {${n/4+\epsilon n}$} contains a Hamilton cycle. Our
bounds
on the minimum degree are essentially best possible. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {273-278},
url = {http://www.dmtcs.org/proceedings/html/dmAE0154.abs.html}
}
@inproceedings{DMTCS-AE0155,
author = {Rajneesh Hegde and Kamal Jain},
title = {A Min-Max theorem about the Road Coloring Conjecture},
keywords = {road coloring, synchronization of automata},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { The Road Coloring Conjecture is an old and classical conjecture posed
in
[adler70,adler77]. Let {${G}$} be a strongly connected digraph
with
uniform out-degree 2. The Road Coloring Conjecture states that, under
a
natural (necessary) condition that {${G}$} is ``aperiodic'',
the
edges of {${G}$} can be colored red and blue such that
``universal
driving directions'' can be given for each vertex. More precisely,
each
vertex has one red and one blue edge leaving it, and for any vertex
{${v}$}
there exists a sequence {${s_{v}}$} of reds and blues
such
that following the sequence from \emph{any} starting vertex in
{${G}$}
ends precisely at the vertex {${v}$}. We first generalize the
conjecture
to a min-max conjecture for all strongly connected digraphs. We then
generalize
the notion of coloring itself. Instead of assigning exactly one color
to
each edge we allow multiple colors to each edge. Under this relaxed
notion
of coloring we prove our generalized Min-Max theorem. Using the Prime
Number
Theorem (PNT) we further show that the number of colors needed for
each
edge is bounded above by {${O(\log n/\log \log n)}$}, where
{${n}$} is the number of vertices in the digraph. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {279-284},
url = {http://www.dmtcs.org/proceedings/html/dmAE0155.abs.html}
}
@inproceedings{DMTCS-AE0156,
author = {Van H. Vu and Lei Wu},
title = {Improving the Gilbert-Varshamov bound for {${q}$}-ary codes},
keywords = { },
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { Given positive integers {${q}$}, {${n}$} and
{${d}$},
denote by {${A_{q}(n,d)}$} the maximum size of a
{${q}$}-ary
code of length {${n}$} and minimum distance {${d}$}. The
famous
Gilbert-Varshamov bound asserts that {${A_{q}(n,d+1)
{\geq}q^{n} / V_{q}(n,d),}$} where
{${V_{q}(n,d)=\sum_{i=0}^{d}\binom{n}{
i}(q-1)^{i}}$}
is the volume of a {${q}$}-ary sphere of radius {${d}$}.
Extending
a recent work of Jiang and Vardy on binary codes, we show that for any
positive
constant {${\alpha }$} less than {${(q-1)/q}$} there is
a
positive constant {${c}$} such that for {${d
{\leq}\alpha n}$}, {${A_{q}(n,d+1){\geq}cq^{n}\,/\,V_{q}(n,d)n}$}. This confirms a conjecture by Jiang and Vardy. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {285-288},
url = {http://www.dmtcs.org/proceedings/html/dmAE0156.abs.html}
}
@inproceedings{DMTCS-AE0157,
author = {Tomoki Nakamigawa},
title = {Equivalent Subgraphs of Order 3},
keywords = {graph Ramsey theory, graph decomposition},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { It is proved that any graph of order {${14n/3 + O(1)}$}
contains
a family of {${n}$} induced subgraphs of order {${3}$}
such
that they are vertex-disjoint and equivalent to each other. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {289-292},
url = {http://www.dmtcs.org/proceedings/html/dmAE0157.abs.html}
}
@inproceedings{DMTCS-AE0158,
author = {Gyula O.H. Katona and Kriszti{\'a}n Tichler},
title = {An extremal problem on trees and database theory},
keywords = {labelled directed tree, relational database, minimum matrix representation, extremal problems},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { We consider an extremal problem on labelled directed trees and
applications
to database theory. Among others, we will show explicit keysystems on
an
underlying set of size {${n}$}, that cannot be represented by a
database
of less than {${2^{n(1-c{\cdot}\log \log n/\log n)}}$}
rows. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {293-298},
url = {http://www.dmtcs.org/proceedings/html/dmAE0158.abs.html}
}
@inproceedings{DMTCS-AE0159,
author = {Miroslava Cimr{\'a}kov{\'a} and Veerle Fack},
title = {On minimal blocking sets of the generalized quadrangle},
keywords = {generalized quadrangle, blocking set, search algorithm},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { The generalized quadrangle {${Q(4,q)}$} arising from the
parabolic
quadric in {${PG(4,q)}$} always has an ovoid. It is not known
whether
a minimal blocking set of size smaller than {${q^{2} +
q}$} (which
is not an ovoid) exists in {${Q(4,q), \ q}$}\ odd. We
present
results on smallest blocking sets in {${Q(4,q),
\ q}$}\ odd,
obtained by a computer search. For {${q = 5,7,9,11}$} we found
minimal
blocking sets of size {${q^{2} + q - 2}$} and we
discuss
their structure. By an exhaustive search we excluded the existence of
a
minimal blocking set of size {${q^{2} + 3}$} in
{${Q(4,7)}$}. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {299-302},
url = {http://www.dmtcs.org/proceedings/html/dmAE0159.abs.html}
}
@inproceedings{DMTCS-AE0160,
author = {Tom{\'a}\v{s} Kaiser and Riste \v{S}krekovski},
title = {Cycles intersecting edge-cuts of prescribed sizes},
keywords = {graph, cycle, edge-cut, covering cycle, coverable set},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { We prove that every cubic bridgeless graph {${G}$} contains a
{${2}$}-factor
which intersects all (minimal) edge-cuts of size {${3}$} or
{${4}$}.
This generalizes an earlier result of the authors, namely that such a
{${2}$}-factor
exists provided that {${G}$} is planar. As a further extension,
we
show that every graph contains a cycle (a union of edge-disjoint
circuits)
that intersects all edge-cuts of size {${3}$} or
{${4}$}.
Motivated by this result, we introduce the concept of a coverable set
of
integers and discuss a number of questions, some of which are related
to
classical problems of graph theory such as Tutte's {${4}$}-flow
conjecture or the Dominating circuit conjecture. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {303-308},
url = {http://www.dmtcs.org/proceedings/html/dmAE0160.abs.html}
}
@inproceedings{DMTCS-AE0161,
author = {Stefanie Gerke and Martin Marciniszyn and Angelika Steger},
title = {A Probabilistic Counting Lemma for Complete Graphs},
keywords = { },
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = { We prove the existence of many complete graphs in almost all
sufficiently
dense partitions obtained by an application of Szemer{\'e}di's
Regularity
Lemma. More precisely, we consider the number of complete graphs
{${K_{{\ell}}}$}
on {${{\ell}}$} vertices in {${{\ell}}$}-partite
graphs
where each partition class consists of {${n}$} vertices and
there
is an {${\epsilon }$}-regular graph on {${m}$} edges
between
any two partition classes. We show that for all\ {${\beta >
0}$},
at most a {${\beta ^{m}}$}-fraction of graphs in this
family
contain less than the expected number of copies of
{${K_{{\ell}}}$}
provided {${\epsilon }$} is sufficiently small and {${m
{\geq}Cn^{2-1/({\ell}-1)}}$}
for a constant\ {${C > 0}$} and {${n}$}
sufficiently
large. This result is a counting version of a restricted version of a
conjecture
by Kohayakawa, {\L}uczak and R{\"o}dl\ [MR1479298] and has
several implications for random graphs. },
series = {DMTCS Proceedings},
publisher = {Discrete Mathematics and Theoretical Computer Science},
year = 2005,
volume = {AE},
pages = {309-316},
url = {http://www.dmtcs.org/proceedings/html/dmAE0161.abs.html}
}
@inproceedings{DMTCS-AE0162,
author = {Francesc Aguil{\'o} and Al\'{\i}cia Miralles},
title = {Frobenius' Problem},
keywords = {Frobenius problem, L-shaped tile, Smith normal form, Minimum Distance Diagram},
editor = {Stefan Felsner},
booktitle = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
abstract = {Given {${k}$} natural numbers {${\{a_{1},...,a_{k}\}{\subset}{\naturals}}$}
with {${1{\leq}a_{1}*