Paper Info
Title
Optimal parallel computations for Halin graphs
Abstract
Optimal parallel algorithms are given for two hard problems (the Hamiltonian cycle and the travelling salesman problem) restricted to graphs having a simple structure — Halin graphs. These problems were previously investigated for Halin graphs from the sequential point of view [1,5,6]. The travelling salesman problem (the computation of the shortest Hamiltonian cycle) for the Halin graph is interesting because such a graph can contain an exponential number of Hamiltonian cycles. Two tree-oriented algorithmic techniques are used: computation of products for paths of the tree (which gives log2n time algorithm for the Hamiltonian cycle) and a special parallel pebble game (giving log2n time for the travelling salesman problem).
Year
DOI
Venue
1989
10.1007/3-540-51859-2_21
Optimal Algorithms
Keywords
Field
DocType
halin graphs,optimal parallel computations,optimal parallel computation,halin graph,parallel algorithm,travelling salesman problem,hamiltonian cycle,parallel computer
Discrete mathematics,Combinatorics,Hamiltonian (quantum mechanics),Parallel random-access machine,Hamiltonian path,Parallel algorithm,Hamiltonian path problem,Travelling salesman problem,Halin graph,Mathematics,Computation
Conference
Volume
ISSN
ISBN
401
0302-9743
0-387-51859-2
Citations 
PageRank 
References 
0
0.34
3
Authors
2
Name
Order
Citations
PageRank
Krzysztof Diks1665.83
wojciech rytter213017.13