//img.uscri.be/pth/262ff1a982d69fe6696177f9dd598c9c199d2d03
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Exact and Parameterized Algorithms for Max Internal Spanning Tree

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


Voir plus Voir moins
WG200912LIRMMUniUvenirvsietrésidtyeoMfoTrnitepr,ellGieerr2m,aCnyNRS,FranceHenningFernau1SergeGaspers2DanielRaible1ExactandParameterizedAlgorithmsforMAXINTERNALSPANNINGTREE12/1noisulcnoCshpargcibucroftluseRgnihcnarBerusaeMseluRnoitacilpmiSmhtiroglAfoeniltuOsnoitavresbO3eergedxamfoshpargrofmhtiroglAstluseRweNstluseRruOstluseRsuoiverPnoitineDmelborPnoitcudortnIsrepsaG.SeerTgninnapSlanretnIxaM
noisulcnoCshpargcibucroftIntroductionProblemDefinitionPreviousResultsOurResultsNewResultsl1u3sConclusione2RAlgorithmforgraphsofmaxdegree3ObservationsOutlineofAlgorithmSimplificationRulesMeasureBranchingResultforcubicgraphsgOutlinenMaxInternalSpanningTreeiIntroductionProblemDefinitionPreviousResultsOurResultsNewResultshcnarBerusaeMseluRnoitacilpmiSmhtiroglAfoeniltuOsnoitavresbO3eergedxamfoshpargrofmhtiroglAsrepsaG.S12/2