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. |
URI: | http://hdl.handle.net/11420/8765 | ISSN: | 0166-218X | Institute: | Mathematik E-10 | Document Type: | Article | Journal: | Discrete applied mathematics |
Appears in Collections: | Publications without fulltext |
Show full item record
Add Files to Item
Note about this record
Cite this record
Export
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.