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

Search Trees and Branching Numbers

De
45 pages
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


Voir plus Voir moins
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. IVis 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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin