All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2

Displaying 21 – 40 of 40

Showing per page

Comparing classification tree structures: A special case of comparing q-ary relations II

I. C. Lerman, F. Rouxel (2010)

RAIRO - Operations Research

Comparing q-ary relations on a set 𝒪 of elementary objects is one of the most fundamental problems of classification and combinatorial data analysis. In this paper the specific comparison task that involves classification tree structures (binary or not) is considered in this context. Two mathematical representations are proposed. One is defined in terms of a weighted binary relation; the second uses a 4-ary relation. The most classical approaches to tree comparison are discussed in the context...

Comparing classification tree structures: a special case of comparing q-ary relations

Israel-Cesar Lerman (2010)

RAIRO - Operations Research

Comparing q-ary relations on a set 𝒪 of elementary objects is one of the most fundamental problems of classification and combinatorial data analysis. In this paper the specific comparison task that involves classification tree structures (binary or not) is considered in this context. Two mathematical representations are proposed. One is defined in terms of a weighted binary relation; the second uses a 4-ary relation. The most classical approaches to tree comparison are discussed in the context...

Completely Independent Spanning Trees in (Partial) k-Trees

Masayoshi Matsushita, Yota Otachi, Toru Araki (2015)

Discussiones Mathematicae Graph Theory

Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T1 and T2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree. First we show that [k/2] ≤ cist(G) ≤ k − 1 for any k-tree G. Then we show that for any p ∈ {[k/2], . . . , k − 1}, there exist infinitely many k-trees G such that cist(G)...

Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs

Sebastian M. Cioabă, Xiaofeng Gu (2016)

Czechoslovak Mathematical Journal

The eigenvalues of graphs are related to many of its combinatorial properties. In his fundamental work, Fiedler showed the close connections between the Laplacian eigenvalues and eigenvectors of a graph and its vertex-connectivity and edge-connectivity. We present some new results describing the connections between the spectrum of a regular graph and other combinatorial parameters such as its generalized connectivity, toughness, and the existence of spanning trees with bounded degree.

Constrained Steiner trees in Halin graphs

Guangting Chen, Rainer E. Burkard (2003)

RAIRO - Operations Research - Recherche Opérationnelle

In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.

Constrained Steiner trees in Halin graphs

Guangting Chen, Rainer E. Burkard (2010)

RAIRO - Operations Research

In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.

Constructions for type I trees with nonisomorphic Perron branches

Stephen J. Kirkland (1999)

Czechoslovak Mathematical Journal

A tree is classified as being type I provided that there are two or more Perron branches at its characteristic vertex. The question arises as to how one might construct such a tree in which the Perron branches at the characteristic vertex are not isomorphic. Motivated by an example of Grone and Merris, we produce a large class of such trees, and show how to construct others from them. We also investigate some of the properties of a subclass of these trees. Throughout, we exploit connections between...

Coxeter polynomials of Salem trees

Charalampos A. Evripidou (2015)

Colloquium Mathematicae

We compute the Coxeter polynomial of a family of Salem trees, and also the limit of the spectral radii of their Coxeter transformations as the number of their vertices tends to infinity. We also prove that if z is a root of multiplicities m ₁ , . . . , m k for the Coxeter polynomials of the trees ₁ , . . . , k respectively, then z is a root for the Coxeter polynomial of their join, of multiplicity at least m i n m - m ₁ , . . . , m - m k where m = m ₁ + ⋯ + m k .

Cutwidth of iterated caterpillars

Lan Lin, Yixun Lin (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

The cutwidth is an important graph-invariant in circuit layout designs. The cutwidth of a graph G is the minimum value of the maximum number of overlap edges when G is embedded into a line. A caterpillar is a tree which yields a path when all its leaves are removed. An iterated caterpillar is a tree which yields a caterpillar when all its leaves are removed. In this paper we present an exact formula for the cutwidth of the iterated caterpillars.

Cutwidth of the r-dimensional Mesh of d-ary Trees

Imrich Vrťo (2010)

RAIRO - Theoretical Informatics and Applications

We prove that the cutwidth of the r-dimensional mesh of d-ary trees is of order Θ ( d ( r - 1 ) n + 1 ) , which improves and generalizes previous results.

Currently displaying 21 – 40 of 40

Previous Page 2