Optimization Problems on Distance Hereditary Graphs

Participants,, Overview, Selected results.



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

Created by Tsan-sheng Hsu, last updated May 21, 2002.