On some polynomial solvable cases of the generalized minimum spanning tree problem.

Pop, Petrică Claudiu

The search session has expired. Please query the service again.

Displaying similar documents to “On some polynomial solvable cases of the generalized minimum spanning tree problem.”

Variations for spanning trees.

Zsakó, László (2006)

Annales Mathematicae et Informaticae

Similarity:

Independence number and degree bounded spanning tree.

Rahman, Mohammad Sohel, Kaykobad, Mohammad (2004)

Applied Mathematics E-Notes [electronic only]

Similarity:

Spanning tree congestion of rook's graphs

Kyohei Kozawa, Yota Otachi (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Kₘ ☐ Kₙ for any m and n.

Spanning trees with leaves bounded by independence number.

Sun, Ling-li (2007)

Applied Mathematics E-Notes [electronic only]

Similarity:

A Note on Spanning Trees for Network Location Problems

Dionisio Pérez-Brito, Nenad Mladenović, José A. Moreno-Pérez (1998)

The Yugoslav Journal of Operations Research

Similarity:

A Bicriterion Steiner Tree Problem on Graph

Mirko Vujošević, Milan Stanojević (2003)

The Yugoslav Journal of Operations Research

Similarity:

A note on the distribution of the three types of nodes in uniform binary trees.

Prodinger, Helmut (1996)

Séminaire Lotharingien de Combinatoire [electronic only]

Similarity:

Completely Independent Spanning Trees in (Partial) k-Trees

Masayoshi Matsushita, Yota Otachi, Toru Araki (2015)

Discussiones Mathematicae Graph Theory

Similarity:

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...

Approximation algorithms for metric tree cover and generalized tour and tree covers

Viet Hung Nguyen (2007)

RAIRO - Operations Research

Similarity:

Given a weighted undirected graph , a tree (respectively tour) cover of an edge-weighted graph is a set of edges which forms a tree (resp. closed walk) and covers every other edge in the graph. The tree (resp. tour) cover problem is of finding a minimum weight tree (resp. tour) cover of . Arkin, Halldórsson and Hassin (1993) give approximation algorithms with factors respectively 3.5 and 5.5. Later Könemann, Konjevod, Parekh, and Sinha (2003) study the linear programming relaxations...

Worst-case relative performances of heuristics for the Steiner problem in graphs.

Plesník, Ján (1991)

Acta Mathematica Universitatis Comenianae. New Series

Similarity:

The color-balanced spanning tree problem

Štefan Berežný, Vladimír Lacko (2005)

Kybernetika

Similarity:

Suppose a graph $G = (V, E)$ whose edges are partitioned into $p$ disjoint categories (colors) is given. In the color-balanced spanning tree problem a spanning tree is looked for that minimizes the variability in the number of edges from different categories. We show that polynomiality of this problem depends on the number $p$ of categories and present some polynomial algorithm.

On the rules for the elimination of the non-canonical Morgan trees

Damir Vukičević (2009)

Kragujevac Journal of Mathematics

Similarity: