Worst-case relative performances of heuristics for the Steiner problem in graphs.
Plesník, Ján (1991)
Acta Mathematica Universitatis Comenianae. New Series
Similarity:
Plesník, Ján (1991)
Acta Mathematica Universitatis Comenianae. New Series
Similarity:
Mirko Vujošević, Milan Stanojević (2003)
The Yugoslav Journal of Operations Research
Similarity:
Diané, M., Plesník, Ján (1991)
Acta Mathematica Universitatis Comenianae. New Series
Similarity:
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...
Guangting Chen, Rainer E. Burkard (2010)
RAIRO - Operations Research
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.
Ján Plesník (1981)
Mathematica Slovaca
Similarity:
Zsakó, László (2006)
Annales Mathematicae et Informaticae
Similarity:
Bryant Julstrom (2004)
International Journal of Applied Mathematics and Computer Science
Similarity:
The features of an evolutionary algorithm that most determine its performance are the coding by which its chromosomes represent candidate solutions to its target problem and the operators that act on that coding. Also, when a problem involves constraints, a coding that represents only valid solutions and operators that preserve that validity represent a smaller search space and result in a more effective search. Two genetic algorithms for the leaf-constrained minimum spanning tree problem...
Dionisio Pérez-Brito, Nenad Mladenović, José A. Moreno-Pérez (1998)
The Yugoslav Journal of Operations Research
Similarity: