Exact and Parameterized Algorithms for Max Internal Spanning Tree

Max Internal

Description

Max Internal Spanning Tree S. Gaspers Introduction Problem Definition Previous Results Our Results New Results Algorithm for graphs of max degree 3 Observations Outline of Algorithm Simplification Rules Measure Branching Result for cubic graphs Conclusion Exact and Parameterized Algorithms for MAX INTERNAL SPANNING TREE Henning Fernau1 Serge Gaspers2 Daniel Raible1 1University of Trier, Germany 2LIRMM – Université de Montpellier 2, CNRS, France WG 2009 1 / 21

• simplification rules


• introduction problem


• algorithm


• maximum internal


• measure


• hamiltonian path


• spanning tree

Sujets

• Université de Montpellier
• Internal
• Algorithm
• Measure
• Hamiltonian path
• Spanning tree

Informations

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

Extrait

WG2009 1 2 LIRMM–Uni U ve ni r v si e t r é si d ty e o M f o Tr n i t e p r, ell G ie e r r 2 m , a C ny NRS,France HenningFernau 1 SergeGaspers 2 DanielRaible 1 ExactandParameterizedAlgorithmsfor M AX I NTERNAL S PANNING T REE 12/1 noisulcnoC shpargcibucroftluseR gnihcnarB erusaeM seluRnoitacfiilpmiS mhtiroglAfoeniltuO snoitavresbO 3eerged xamfoshparg rofmhtiroglA stluseRweN stluseRruO stluseRsuoiverP noitinfieDmelborP noitcudortnI srepsaG.S eerTgninnapS lanretnIxaM

noisulcnoC shpargcibucroft Introduction ProblemDefinition PreviousResults OurResults NewResults l 1 u 3 s Conclusion e 2 R Algorithmforgraphsofmaxdegree3 Observations OutlineofAlgorithm SimplificationRules Measure Branching Resultforcubicgraphs g Outline n MaxInternal SpanningTree i Introduction ProblemDefinition PreviousResults OurResults NewResults hcnarB erusaeM seluRnoitacfiilpmiS mhtiroglAfoeniltuO snoitavresbO 3eerged xamfoshparg rofmhtiroglA srepsaG.S 12/2