Directed Graph Minors and Serial-Parallel Width

Deligkas, Argyrios and Meir, Reshef (2017) Directed Graph Minors and Serial-Parallel Width. .

Access the full-text of this item by clicking on the Open Access link.

Official URL: http://www.dagstuhl.de/dagpub/978-3-95977-086-6

Abstract

Graph minors are a primary tool in understanding the structure of undirected graphs, with many conceptual and algorithmic implications. We propose new variants of \emph{directed graph minors} and \emph{directed graph embeddings}, by modifying familiar definitions. For the class of 2-terminal directed acyclic graphs (TDAGs) our two definitions coincide, and the class is closed under both operations. The usefulness of our directed minor operations is demonstrated by characterizing all TDAGs with serial-parallel width at most $k$; a class of networks known to guarantee bounded negative externality in nonatomic routing games. Our characterization implies that a TDAG has serial-parallel width of $1$ if and only if it is a directed series-parallel graph. We also study the computational complexity of finding a directed minor and computing the serial-parallel width.

Item Type:	Conference or Workshop Item (Unspecified)
Additional Information:	published in MFCS 2018
Uncontrolled Keywords:	cs.DM, cs.DM, math.CO, F.2.2; G.2.2
Depositing User:	Symplectic Admin
Date Deposited:	11 Feb 2019 14:16
Last Modified:	22 Nov 2023 13:37
DOI:	10.4230/LIPIcs.MFCS.2018.44
Open Access URL:	http://drops.dagstuhl.de/opus/volltexte/2018/9626/...
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3032655