An algorithmic study of switch graphs

Bastian Katz1

Description

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

Sujets

• Karlsruhe
• Computer science

Informations

• Publié par: pefav
• Nombre de lectures: 22
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

An algorithmic study of switch graphs

Bastian Katz 1

Ignaz Rutter 1

1 Algorithmics Group Faculty of Informatics Universita¨tKarlsruhe(TH),KIT

Gerhard J. Woeginger 2

2 Department 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 p s ∈Vis thepivotvertex

∅ 6=T s ⊆V

may

Global Connectivity

pair (p s ,T s ).

is the set oftargetvertices

enable exactly

Algorithmic Group Faculty of Informatics

one

of

the

edges{{p s ,t s

} |t s

∈T s

}

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 p s ∈Vis thepivotvertex

∅ 6=T s ⊆V

may

Global Connectivity

pair (p s ,T s ).

is the set oftargetvertices

enable exactly

Algorithmic Group Faculty of Informatics

one

of

the

edges{{p s ,t s

} |t s

∈T s

}

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 p s ∈Vis thepivotvertex

∅ 6=T s ⊆V

may

Global Connectivity

pair (p s ,T s ).

is the set oftargetvertices

enable exactly

Algorithmic Group Faculty of Informatics

one

of

the

edges{{p s ,t s

} |t s

∈T s

}

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:S→V

Algorithmic Group Faculty of Informatics

s.t.c(s)∈T s

Local Connectivitiy

∀s∈S.

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:S→Vs.t.c(s)∈T s ∀s∈S. cpicks exactly one edgee c (s) :={p s ,c(s)}for every switchs. Yields multigraphG c = (V,E c ) withE c ={e c (s) :s∈S}.

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:S→Vs.t.c(s)∈T s ∀s∈S. cpicks exactly one edgee c (s) :={p s ,c(s)}for every switchs. Yields multigraphG c = (V,E c ) withE c ={e c (s) :s∈S}.

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:= max s∈S |T s |. Question: DoesGhave a configurationcsuch thatG c has 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