Optimization Problems on Distance Hereditary Graphs
Participants,,
Overview,
Selected results.
Participants
- IIS members:
- Outside members:
-
Gen-Huey Chen, Department of Computer Science and Information
Engineering, National Taiwan University.
-
Chin-Wen Ho, Department of Computer Science and Information
Engineering, National Central University.
- Sun-yuan Hsieh, Department of Computer Science and Information
Engineering, National Chi Nan University.
Overview
A graph is distance-hereditary
if the distance stays the same between any of two vertices in
every connected induced subgraph containing both
(where the distance between two vertices is the length
of a shortest path connecting them).
Two well-known classes of graphs,
trees and cographs, both belong to distance-hereditary graphs.
Properties of distance-hereditary graphs are studied by
many researchers.
In this series of research, we discover fundamental parallel primitives
that can be used to design efficient parallel algorithms for
optimization problems on this class of graphs.
These parallel primitives have a potential to be used to
solve other graph-theoretical problems.
Selected results
-
Sun-yuan Hsieh, Chin-Wen Ho, Tsan-sheng Hsu, and Ming-Tat Ko,
"Efficient Algorithms for the Hamiltonian Problem on
Distance-Hereditary Graphs",
Proceedings of the 8th International Computing and Combinatorics
Conference (COCOON),
to appear in a Springer-Verlag LNCS volume, 2002.
-
This paper gives sequential and parallel algorithms for solving the
Hamiltonian problem on distance-hereditary graphs.
-
Sun-yuan Hsieh, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, and Gen-Huey Chen,
``Efficient Parallel Algorithms on Distance-Hereditary Graphs,''
Parallel Processing Letters, volume 9, pages 43--52, 1999.
Extended abstract in
Proc. International Conference on Parallel Processing
(ICPP), pages 20--23, 1997.
-
In this paper, we first devise very simple parallel techniques
by reducing several optimization problems into the problems
of lexicographically sorting and Euler-tour techniques.
-
Sun-yuan Hsieh, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, and Gen-Huey Chen,
"A New Simple Parallel Tree Contraction Scheme and Its Application
on Distance-Hereditary Graphs,"
Journal of Algorithms, volume 35, pages 50--81, 2000.
Extended abstract in
Proc. 5th International Workshop on
Parallel Algorithms for Irregularly Structured Problems (IRR),
Springer-Verlag LNCS #1457, pages 298--309, 1998.
-
In this paper, we discover a new and much faster implementation
of the tree contraction scheme
which in each contraction phase removes leaves and nodes in the
maximal chains.
Previous implementation requires $O(\log^2 n)$ parallel time.
Our implementation takes $O(\log n \log\log\log n)$ time.
Using this technique, we have successfully solved
several optimization problems in this parallel time complexity.
Since this type of tree contraction is fundamental in many other researches,
it is likely that our technique can be used by others to improve their
algorithms.
-
Sun-yuan Hsieh, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, and Gen-Huey Chen,
"Characterization of Efficiently Computable Problems on
Distance-Hereditary Graphs,"
Proc. 8th International Symposium on Algorithms and
Computation (ISAAC), Springer-Verlag LNCS # 1533, pages 257--266,
1998.
-
In this paper, we further discover a new paradigm
for solving optimization problems on distance-hereditary graphs.
This paradigm generalizes the technique of
arithmetic expression evaluation using tree contraction.
In the generalization, each operand of the expression is
a set of values. Using this generalization as a basis, we have
successfully solved several graph-optimization problems
with better complexities.
Created by Tsan-sheng Hsu, last updated May 21, 2002.