Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2014 | OriginalPaper | Chapter

Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract)

Authors : Reinhard Diestel, Sang-il Oum

Published in: Graph-Theoretic Concepts in Computer Science

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We prove a general duality theorem for width parameters in combinatorial structures such as graphs and matroids. It implies the classical such theorems for path-width, tree-width, branch-width and rank-width, and gives rise to new width parameters with associated duality theorems. The dense substructures witnessing large width are presented in a unified way akin to tangles, as orientations of separation systems satisfying certain consistency axioms.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
next chapter Distributedly Testing Cycle-Freeness
Footnotes
1
In fact, we need even less. It would be enough to consider instead of ‘separations’ any poset with an involution that commutes with its ordering, just as the ordering of separations introduced below satisfies \((A,B)\le (C,D) \Leftrightarrow (B,A)\ge (D,C)\). It is only for the sake of readability that we are writing this paper in terms of separations, as readers are likely to have graphs or matroids in mind.
 
2
Our notational convention will be that we think of \((A,B)\) as pointing towards \(B\).
 
3
It is a good idea to work with this formal definition of consistency, since the more intuitive notion of ‘pointing away from each other’ can be counterintuitive. For example, we shall need that no consistent set of separations of \(V\) contains a separation of the form \((V,A)\); this follows readily from the formal definition, as \((A,V)\le (V,A)\), but is less obvious from the informal.
 
4
This will help us show that \((T,\alpha ')\) is over \(\mathcal F\) if \((T,\alpha )\) is.
 
5
This will help us show that \((T,\alpha ')\) is rooted in \(S^-\) if \((T,\alpha )\) is.
 
6
For example, we do not need Menger’s theorem, as all the other proofs do.
 
7
In our matroid terminology we follow Oxley [9].
 
Literature
1.
Amini, O., Mazoit, F., Nisse, N., Thomassé, S.: Submodular partition functions. Discrete Appl. Math. 309(20), 6000–6008 (2009)CrossRefMATH
2.
Bienstock, D., Robertson, N., Seymour, P., Thomas, R.: Quickly excluding a forest. J. Combin. Theor. Ser. B 52(2), 274–283 (1991)MathSciNetCrossRefMATH
3.
4.
Geelen, J., Gerards, B., Robertson, N., Whittle, G.: Obstructions to branch-decomposition of matroids. J. Combin. Theor. Ser. B 96, 560–570 (2006)MathSciNetCrossRefMATH
5.
6.
7.
8.
9.
Oxley, J.: Matroid Theory. Oxford University Press, Oxford (1992)MATH
10.
11.
12.
Metadata
Title
Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract)
Authors
Reinhard Diestel
Sang-il Oum
Copyright Year
2014
Book
Graph-Theoretic Concepts in Computer Science

Print ISBN: 978-3-319-12339-4

Electronic ISBN: 978-3-319-12340-0

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-12340-0_1

Premium Partner

    Image Credits