111 Pages
English
Gain access to the library to view online
Learn more

Graph Minors and algorithms The irrelevant vertex technique

Gain access to the library to view online
Learn more
111 Pages
English

Description

Graph Minors and algorithms The irrelevant vertex technique Algorithmic Graph Minors: turning Combinatorics to Algorithms Dimitrios M. Thilikos Department of Mathematics – µ∏?? UoA - National and Kapodistrian University of Athens Laboratoire d'Informatique, de Robotique et de Microelectronique de Montpellier (LIRMM) Montpellier, February 2, 2012 Dimitrios M. Thilikos Department of Mathematics, UoA Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 1/111 1

  • ordering theory

  • component-wise ordering

  • vertex technique

  • minors

  • microelectronique de montpellier

  • algorithmic graph

  • has no


Subjects

Informations

Published by
Reads 48
Language English
Document size 1 MB

Exrait

Graph Minors and algorithms The irrelevant vertex technique
Algorithmic Graph Minors:
turning Combinatorics to Algorithms
Dimitrios M. Thilikos
Q
Department of Mathematics { 8
UoA - National and Kapodistrian University of Athens
Laboratoire d’Informatique, de Robotique et de Microelectronique de Montpellier
(LIRMM)
Montpellier, February 2, 2012
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 1/111 1Antichain: an in nite sequence on non- -comparable elements.
We say thatX is Well-Quasi-Ordered by if it has no in nite
antichain
Examples:
NI 2 is not W.Q.O. by set inclusion.
IN is not W.Q.O. by divisibility.
kIN is W.Q.O. by by component-wise ordering.
Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
LetX be a set and let \" be a partial ordering relation onX .
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 2/111 2We say thatX is Well-Quasi-Ordered by if it has no in nite
antichain
Examples:
NI 2 is not W.Q.O. by set inclusion.
IN is not W.Q.O. by divisibility.
kIN is W.Q.O. by by component-wise ordering.
Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
LetX be a set and let \" be a partial ordering relation onX .
Antichain: an in nite sequence on non- -comparable elements.
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 3/111 2Examples:
NI 2 is not W.Q.O. by set inclusion.
IN is not W.Q.O. by divisibility.
kIN is W.Q.O. by by component-wise ordering.
Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
LetX be a set and let \" be a partial ordering relation onX .
Antichain: an in nite sequence on non- -comparable elements.
We say thatX is Well-Quasi-Ordered by if it has no in nite
antichain
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 4/111 2Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
LetX be a set and let \" be a partial ordering relation onX .
Antichain: an in nite sequence on non- -comparable elements.
We say thatX is Well-Quasi-Ordered by if it has no in nite
antichain
Examples:
NI 2 is not W.Q.O. by set inclusion.
IN is not W.Q.O. by divisibility.
kIN is W.Q.O. by by component-wise ordering.
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 5/111 2The theory of Well-quasi-ordering was rst developed by
Graham Higman and Erd} os & Rado
under the name \ nite basis property"
Remind: This talk is about graphs and algorithms!
Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
General question: Given a setX and an ordering relation on it,
isX W.Q.O. by to?
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 6/111 3Remind: This talk is about graphs and algorithms!
Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
General question: Given a setX and an ordering relation on it,
isX W.Q.O. by to?
The theory of Well-quasi-ordering was rst developed by
Graham Higman and Erd} os & Rado
under the name \ nite basis property"
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 7/111 3Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
General question: Given a setX and an ordering relation on it,
isX W.Q.O. by to?
The theory of Well-quasi-ordering was rst developed by
Graham Higman and Erd} os & Rado
under the name \ nite basis property"
Remind: This talk is about graphs and algorithms!
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 8/111 3v
1 nv: vertex removal:
e
2 ne: edge removal:
e
3 =e: edge contraction
Minor Relation:
HG if H can be obtained from G after a sequence of the above operations
Graph Minors and algorithms The irrelevant vertex technique
The minor relation on Graphs
Graph Minors
We de ne 3 local operations on graphs:
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 9/111 4e
2 ne: edge removal:
e
3 =e: edge contraction
Minor Relation:
HG if H can be obtained from G after a sequence of the above operations
Graph Minors and algorithms The irrelevant vertex technique
The minor relation on Graphs
Graph Minors
We de ne 3 local operations on graphs:
v
1 nv: vertex removal:
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 10/111 4