DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2018.44

Directed Graph Minors and Serial-Parallel Width

Authors: Argyrios Deligkas and Reshef Meir

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

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 directed graph minors and 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.

Cite as

Argyrios Deligkas and Reshef Meir. Directed Graph Minors and Serial-Parallel Width. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{deligkas_et_al:LIPIcs.MFCS.2018.44,
  author =	{Deligkas, Argyrios and Meir, Reshef},
  title =	{{Directed Graph Minors and Serial-Parallel Width}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.44},
  URN =		{urn:nbn:de:0030-drops-96261},
  doi =		{10.4230/LIPIcs.MFCS.2018.44},
  annote =	{Keywords: directed minors, pathwidth}
}

Search Results

Documents authored by Meir, Reshef

Directed Graph Minors and Serial-Parallel Width

Abstract

Cite as

Thanks for your feedback!

Could not send message