Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

An algorithmic study of switch graphs

De
114 pages
An algorithmic study of switch graphs Bastian Katz1 Ignaz Rutter1 Gerhard J. Woeginger2 1 Algorithmics Group Faculty of Informatics Universitat Karlsruhe (TH), KIT 2 Department of Mathematics and Computer Science TU Eindhoven June 26, WG 2009

  • karlsruhe

  • switch graphs

  • ignaz rutter

  • ps ?

  • technology universitat

  • target vertices

  • enable exactly

  • computer science


Voir plus Voir moins
An algorithmic study of switch graphs
Bastian Katz1
Ignaz Rutter1
1Algorithmics Group Faculty of Informatics Universita¨tKarlsruhe(TH),KIT
Gerhard J. Woeginger2
2Department of Mathematics and Computer Science TU Eindhoven
June 26, WG 2009
Introduction
What
is
a
SwitchPlanar
switch?
Definition (Switch)
As
We
witchon a vertex setVis a psVis thepivotvertex
∅ 6=TsV
may
Global Connectivity
pair (ps,Ts).
is the set oftargetvertices
enable exactly
Algorithmic Group Faculty of Informatics
one
of
the
edges{{ps,ts
} |ts
Ts
}
Local Connectivitiy
Bastian Katz, Ignaz Rutter, Gerhard Woeginger – Switch Graphs
Karlsruhe Institute of Technology Universit¨atKarlsruhe
2/ 23
Introduction
What
is
a
SwitchPlanar
switch?
Definition (Switch)
As
We
witchon a vertex setVis a psVis thepivotvertex
∅ 6=TsV
may
Global Connectivity
pair (ps,Ts).
is the set oftargetvertices
enable exactly
Algorithmic Group Faculty of Informatics
one
of
the
edges{{ps,ts
} |ts
Ts
}
Local Connectivitiy
Bastian Katz, Ignaz Rutter, Gerhard Woeginger – Switch Graphs
Karlsruhe Institute of Technology Universita¨tKarlsruhe
2/ 23
Introduction
What
is
a
SwitchPlanar
switch?
Definition (Switch)
As
We
witchon a vertex setVis a psVis thepivotvertex
∅ 6=TsV
may
Global Connectivity
pair (ps,Ts).
is the set oftargetvertices
enable exactly
Algorithmic Group Faculty of Informatics
one
of
the
edges{{ps,ts
} |ts
Ts
}
Local Connectivitiy
Bastian Katz, Ignaz Rutter, Gerhard Woeginger – Switch Graphs
Karlsruhe Institute of Technology Universit¨atKarlsruhe
2/ 23
Introduction
SwitchPlanar
What is a switch graph?
Switch graph G= (V,S):
Algorithmic Group Faculty of Informatics
Global Connectivity
Sset of switches on vertex setV.
Bastian Katz, Ignaz Rutter, Gerhard Wo
Karlsruhe Institute of Technology Universit¨atKarlsruhe
Local Connectivitiy
eginger – Switch Graphs
3/ 23
Introduction
SwitchPlanar
What is a switch graph?
Switch graph G= (V,S):
Algorithmic Group Faculty of Informatics
Global Connectivity
Sset of switches on vertex setV.
Bastian Katz, Ignaz Rutter, Gerhard Wo
Karlsruhe Institute of Technology Universit¨atKarlsruhe
Local Connectivitiy
eginger – Switch Graphs
3/ 23
Introduction
SwitchPlanar
What is a switch graph?
Switch graph G= (V,S):
Global Connectivity
Sset of switches on vertex setV.
Aconfigurationis a mappingc:SV
Algorithmic Group Faculty of Informatics
s.t.c(s)Ts
Local Connectivitiy
sS.
Bastian Katz, Ignaz Rutter, Gerhard Woeginger – Switch Graphs
Karlsruhe Institute of Technology Universita¨tKarlsruhe
3/ 23
Introduction
SwitchPlanar
What is a switch graph?
Global Connectivity
Switch graph G= (V,S):Sset of switches on vertex setV.
Local Connectivitiy
Aconfigurationis a mappingc:SVs.t.c(s)TssS. cpicks exactly one edgeec(s) :={ps,c(s)}for every switchs. Yields multigraphGc= (V,Ec) withEc={ec(s) :sS}.
Algorithmic Group Faculty of Informatics
Bastian Katz, Ignaz Rutter, Gerhard Woeginger – Switch Graphs
Karlsruhe Institute of Technology Universit¨atKarlsruhe
3/ 23
Introduction
SwitchPlanar
What is a switch graph?
Global Connectivity
Switch graph G= (V,S):Sset of switches on vertex setV.
Local Connectivitiy
Aconfigurationis a mappingc:SVs.t.c(s)TssS. cpicks exactly one edgeec(s) :={ps,c(s)}for every switchs. Yields multigraphGc= (V,Ec) withEc={ec(s) :sS}.
A switch graph represents a population of graphs, a configuration describes a concrete member of that family.
Algorithmic Group Faculty of Informatics
Bastian Katz, Ignaz Rutter, Gerhard Woeginger – Switch Graphs
Karlsruhe Institute of Technology Universitat Karlsruhe ¨
3/ 23
Introduction
SwitchPlanar
Problems on switch graphs
Global Connectivity
Local Connectivitiy
Every graph propertyPyields problem on switch graphs: ProblemSwitch-P Input: Switch graphG= (V,S) withn:=|V|,m:=|S|and fan-out k:= maxsS|Ts|. Question: DoesGhave a configurationcsuch thatGchas propertyP?
Bipartiteness Global Connectivity Local Connectivity (given verticesa,bare connected) Biconnectivity Planarity Eulerianness Acyclicity
Algorithmic Group Faculty of Informatics
Bastian Katz, Ignaz Rutter, Gerhard Woeginger – Switch Graphs
Karlsruhe Institute of Technology Universit¨atKarlsruhe
4/ 23