@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