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.


Actions:
Full text not available from this repository. (Request a copy)
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: No citation data.
Uncontrolled Keywords: distance distance-hereditary graphs recognition problem
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C12 Distance in graphs

    		•
    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:
    Deposit Information:
    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