Search Trees and Branching Numbers
45
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
45
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
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
Voir
- subinstances
- parameterized complexity
- initial instance
- branching numbers
- can take
- maximum independent
- subinstance branching
- measure based
- instance based
1 / 45
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
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
MXAUMIM
MAXIMUM
4 / 45
ITENNDPEDEN
SET
INDEPENDENTSET(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
