Distance-hereditary digraphs
Lätsch, Martin and Schrader, Rainer
(2010)
Distance-hereditary digraphs.
Published in:
Journal of Disrete Algorithms Vol. 8 (2).
pp. 231-240.
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,{+,*})-distance-hereditary digraphs we give characterizations and provide computational complexity results for the corresponding recognition problems.
Editorial actions: | ![]() |
---|
Item Type: | Article |
---|---|
Citations: | No citation data. |
Uncontrolled Keywords: | distance distance-hereditary graphs recognition problem |
Subjects: |
|
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader Mathematical Institute > Prof. Dr. Faigle |
Additional Information: | Selected papers from the 3rd Algorithms and Complexity in Durham Workshop ACiD 2007 |
Related URLs: |
ZAIK Number: | zaik2011-624 |
---|---|
Depositing User: | Martin Lätsch |
Date Deposited: | 08 Jun 2011 00:00 |
Last Modified: | 24 Oct 2011 13:49 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/624 |