Universität zu Köln

Dornemann, Jorin and Schrader, Rainer (2021). Cross-series-parallel digraphs. Discret Appl. Math., 303. S. 57 - 66. AMSTERDAM: ELSEVIER. ISSN 1872-6771

Full text not available from this repository.

Abstract

Series-parallel directed graphs have been generalized in various directions. Some of these generalizations control the structure of certain emerging induced subdigraphs called N's. They allow an efficient recognition by decomposition trees. We introduce another class of directed acyclic digraphs generalizing series-parallel directed graphs with less structure of induced N's. We show that they still can be efficiently recognized by a decomposition approach. In contrast, however, to the other mentioned generalization this decomposition is not unique and does not lead to a tree but a planar graph. (C) 2020 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Dornemann, Jorin UNSPECIFIED UNSPECIFIED UNSPECIFIED Schrader, Rainer UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-573489
DOI:	10.1016/j.dam.2020.12.012
Journal or Publication Title:	Discret Appl. Math.
Volume:	303
Page Range:	S. 57 - 66
Date:	2021
Publisher:	ELSEVIER
Place of Publication:	AMSTERDAM
ISSN:	1872-6771
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language N-FREE POSETS; TREE-REPRESENTATION; RECOGNITION; ALGORITHMS; COMPLEXITY Multiple languages Mathematics, Applied Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/57348