Search Trees and Branching Numbers

Time Subroutines

Description

Branching algorithms S. Gaspers Introduction Simple Analysis Measure Based Analysis Optimizing the measure Search Trees and Branching Numbers Exponential Time Subroutines Towards a tighter analysis Structures that arise rarely State Based Measures Measure Based Analysis for Parameterized Complexity Analysis of Branching Algorithms séminaire AlGco Serge Gaspers1 1LIRMM – Université Montpellier 2, CNRS Nothing is particularly hard if you divide it into small jobs. – Henry Ford (1863–1947) March 26, 2009 1 / 45

• subinstances


• parameterized complexity


• initial instance


• branching numbers


• can take


• maximum independent


• subinstance branching


• measure based


• instance based

Sujets

• University of Montpellier
• Subroutine
• Parameterized complexity

Informations

• Publié par: pefav
• Nombre de lectures: 17
• Langue: English

Extrait

1 / 45

Analysis

of Branching Algorithms séminaire AlGco

Serge Gaspers 1

1 LIRMM – Université Montpellier 2, CNRS

Nothing is particularly hard if you divide it into small jobs. – Henry Ford(1863–1947)

March 26, 2009

Branching algorithms

S. Gaspers

Introduction

Simple Analysis

Measure Based Analysis

Optimizing the measure

Search Trees and Branching Numbers

Exponential Time Subroutines

Towards a tighter analysis Structures that arise rarely State Based Measures

Measure Based Analysis for Parameterized Complexity

Outline

1

2

3

4

5

6

7

8

2 / 45

Introduction

Simple Analysis

Measure Based Analysis

Optimizing the measure

Search Trees and Branching Numbers

Exponential Time Subroutines

Towards a tighter analysis Structures that arise rarely State Based Measures

Measure Based Analysis for Parameterized Complexity

Branching algorithms

S. Gaspers

Introduction

Simple Analysis

Measure Based Analysis

Optimizing the measure

Search Trees and Branching Numbers

Exponential Time Subroutines

Towards a tighter analysis Structures that arise rarely State Based Measures

Measure Based Analysis for Parameterized Complexity

Outline

1

2

3

4

5

6

7

8

3 / 45

Introduction

Simple Analysis

Measure Based Analysis

Optimizing the measure

Search Trees and Branching Numbers

Exponential Time Subroutines

Towards a tighter analysis Structures that arise rarely State Based Measures

Measure Based Analysis for Parameterized Complexity

Branching algorithms

S. Gaspers

Introduction

Simple Analysis

Measure Based Analysis

Optimizing the measure

Search Trees and Branching Numbers

Exponential Time Subroutines

Towards a tighter analysis Structures that arise rarely State Based Measures

Measure Based Analysis for Parameterized Complexity

M XAUMIM

M AXIMUM

4 / 45

I TENNDPEDEN

S ET

I NDEPENDENT S ET (MIS)

Input: A graphG= (V,E). Output: An independent set ofGof maximum cardinality. I⊆Vis anindependent setif the vertices inIare pairwis non-adjacent.

c

a

d

f

b

e

g

h

e

Branching algorithms

S. Gaspers

Introduction

Simple Analysis

Measure Based Analysis

Optimizing the measure

Search Trees and Branching Numbers

Exponential Time Subroutines

Towards a tighter analysis Structures that arise rarely State Based Measures

Measure Based Analysis for Parameterized Complexity