Publisher DOI: 10.1016/j.dam.2020.12.012
Title: Cross–series–parallel digraphs
Language: English
Authors: Dornemann, Jorin  
Schrader, Rainer 
Keywords: Church–Rosser property;Decomposition;Directed graph;Series–parallel
Issue Date: 15-Nov-2021
Source: Discrete Applied Mathematics 303: 57-65 (2021-11-15)
Abstract (english): 
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.
ISSN: 0166-218X
Institute: Mathematik E-10 
Document Type: Article
Journal: Discrete applied mathematics 
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Jun 27, 2022

Google ScholarTM


Add Files to Item

Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.