Constrained Steiner trees in Halin graphs

Guangting Chen; Rainer E. Burkard

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

Displaying similar documents to “Constrained Steiner trees in Halin graphs”

Constrained Steiner trees in Halin graphs

Guangting Chen, Rainer E. Burkard (2003)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

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.

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

Plesník, Ján (1991)

Acta Mathematica Universitatis Comenianae. New Series

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.

Minimum congestion spanning trees of grids and discrete toruses

Alberto Castejón, Mikhail I. Ostrovskii (2009)

Discussiones Mathematicae Graph Theory

Similarity:

The paper is devoted to estimates of the spanning tree congestion for grid graphs and discrete toruses of dimensions two and three.

2-placement of (p,q)-trees

Beata Orchel (2003)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (L,R;E) be a bipartite graph such that V(G) = L∪R, |L| = p and |R| = q. G is called (p,q)-tree if G is connected and |E(G)| = p+q-1. Let G = (L,R;E) and H = (L',R';E') be two (p,q)-tree. A bijection f:L ∪ R → L' ∪ R' is said to be a biplacement of G and H if f(L) = L' and f(x)f(y) ∉ E' for every edge xy of G. A biplacement of G and its copy is called 2-placement of G. A bipartite graph G is 2-placeable if G has a 2-placement. In this paper we give all (p,q)-trees...

Variations for spanning trees.

Zsakó, László (2006)

Annales Mathematicae et Informaticae

Similarity:

A Bicriterion Steiner Tree Problem on Graph

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

The Yugoslav Journal of Operations Research

Similarity:

Forest decompositions of graphs with cyclomatic number 3.

Farrell, E.J. (1983)

International Journal of Mathematics and Mathematical Sciences

Similarity:

Forest decompositions of graphs with cyclomatic number 2.

Farrell, E.J. (1983)

International Journal of Mathematics and Mathematical Sciences

Similarity:

An Application of Circuit Polynomials to the Counting of Spanning Trees in Graphs

E.J. Farrell, J.C. Grell (1986)

Publications de l'Institut Mathématique

Similarity:

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

Independence number and degree bounded spanning tree.

Rahman, Mohammad Sohel, Kaykobad, Mohammad (2004)

Applied Mathematics E-Notes [electronic only]

Similarity: