Optimization Problems on Distance Hereditary Graphs
Participants,,
Overview,
Selected results.
Participants
 IIS members:
 Outside members:

GenHuey Chen, Department of Computer Science and Information
Engineering, National Taiwan University.

ChinWen Ho, Department of Computer Science and Information
Engineering, National Central University.
 Sunyuan Hsieh, Department of Computer Science and Information
Engineering, National Chi Nan University.
Overview
A graph is distancehereditary
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 wellknown classes of graphs,
trees and cographs, both belong to distancehereditary graphs.
Properties of distancehereditary 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 graphtheoretical problems.
Selected results

Sunyuan Hsieh, ChinWen Ho, Tsansheng Hsu, and MingTat Ko,
"Efficient Algorithms for the Hamiltonian Problem on
DistanceHereditary Graphs",
Proceedings of the 8th International Computing and Combinatorics
Conference (COCOON),
to appear in a SpringerVerlag LNCS volume, 2002.

This paper gives sequential and parallel algorithms for solving the
Hamiltonian problem on distancehereditary graphs.

Sunyuan Hsieh, ChinWen Ho, Tsansheng Hsu, MingTat Ko, and GenHuey Chen,
``Efficient Parallel Algorithms on DistanceHereditary Graphs,''
Parallel Processing Letters, volume 9, pages 4352, 1999.
Extended abstract in
Proc. International Conference on Parallel Processing
(ICPP), pages 2023, 1997.

In this paper, we first devise very simple parallel techniques
by reducing several optimization problems into the problems
of lexicographically sorting and Eulertour techniques.

Sunyuan Hsieh, ChinWen Ho, Tsansheng Hsu, MingTat Ko, and GenHuey Chen,
"A New Simple Parallel Tree Contraction Scheme and Its Application
on DistanceHereditary Graphs,"
Journal of Algorithms, volume 35, pages 5081, 2000.
Extended abstract in
Proc. 5th International Workshop on
Parallel Algorithms for Irregularly Structured Problems (IRR),
SpringerVerlag LNCS #1457, pages 298309, 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.

Sunyuan Hsieh, ChinWen Ho, Tsansheng Hsu, MingTat Ko, and GenHuey Chen,
"Characterization of Efficiently Computable Problems on
DistanceHereditary Graphs,"
Proc. 8th International Symposium on Algorithms and
Computation (ISAAC), SpringerVerlag LNCS # 1533, pages 257266,
1998.

In this paper, we further discover a new paradigm
for solving optimization problems on distancehereditary 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 graphoptimization problems
with better complexities.
Created by Tsansheng Hsu, last updated May 21, 2002.