Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430623 | Journal of Discrete Algorithms | 2010 | 10 Pages |
Abstract
Extending notions from undirected graphs, we introduce directed graphs with the property that distances are preserved when taking induced subdigraphs. We characterize these distance-hereditary digraphs in terms of paths, their level structure and forbidden induced subdigraphs. Weaker requirements than the preservation of distances allow the distance to increase by a multiplicative or additive constant. For these (k,{+,∗})(k,{+,∗})-distance-hereditary digraphs we give characterizations and provide computational complexity results for the corresponding recognition problems.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Martin Lätsch, Rainer Schrader,