id: 01303031
dt: a
an: 01303031
au: Hsieh, Sun-Yuan; Ho, Chin-Wen; Hsu, Tsan-Sheng; Ko, Ming-Tat; Chen,
    Gen-Huey
ti: Characterization of efficiently solvable problems on distance-hereditary
    graphs.
so: Chwa, Kyung-Yong (ed.) et al., Algorithms and computation. 9th
    international symposium, ISAAC ’98. Taejon, Korea, December 14-16,
    1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1533,
    257-266 (1998).
py: 1998
pu: Berlin: Springer
la: EN
cc: 
ut: distance-hereditary graph
ci: 
li: 
ab: Summary: In the literature, there are quite a few sequential and parallel
    algorithms to solve problems in a distance-hereditary graph $G$
    utilizing techniques discovered from the properties of the problems.
    Based on structural properties of $G$, we first sketch characteristics
    of problems which can be systematic solved on $G$ and then define a
    general problem-solving paradigm. Given a decomposition tree
    representation of $G$, we propose a unified approach to construct
    sequential dynamic-programming algorithms for several fundamental
    graph-theoretical problems that fit into our paradigm. We also show
    that our sequential solutions can be efficiently parallelized using the
    tree contraction technique.
rv: