Verlagslink DOI: 10.1016/j.dam.2020.12.012
Titel: Cross–series–parallel digraphs
Sprache: Englisch
Autor/Autorin: Dornemann, Jorin  
Schrader, Rainer 
Schlagwörter: Church–Rosser property; Decomposition; Directed graph; Series–parallel
Erscheinungs­datum: 15-Nov-2021
Quellenangabe: Discrete Applied Mathematics 303: 57-65 (2021-11-15)
Zusammenfassung (englisch): 
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
Zeitschrift: Discrete applied mathematics 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige

Seitenansichten

75
Letzte Woche
0
Letzten Monat
2
checked on 01.10.2022

Google ScholarTM

Prüfe

Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.