A Unified Approach for Solving Vertex Partitioning Problems in Polynomial Time

A Unified Approach for Solving Vertex Partitioning Problems in Polynomial Time

-

Documents
33 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Introduction and definitions Some results Conclusion A Unified Approach for Solving Vertex Partitioning Problems in Polynomial Time Remy Belmonte Martin Vatshelle Department of Informatics, University of Bergen, Norway 2nd Workshop on Graph Decompositions Theoretical, Algorithmic and Logical Aspects October 19, 2010 Remy Belmonte, Martin Vatshelle University of Bergen Solving Vertex Partitioning Problems 1/ 33

  • vertex partitioning

  • bergen solving

  • tolerance strongly

  • trivially perfect

  • perfect comparability

  • bounded tolerance

  • k?trapezoid circular

  • polynomial time


Sujets

Informations

Publié par
Ajouté le 19 juin 2012
Nombre de lectures 17
Langue English
Signaler un abus
Re´myBelmonteMartinVatshelleDepartmentofInformatics,UniversityofBergen,Norway2ndWorkshoponGraphDecompositionsTheoretical,AlgorithmicandLogicalAspectsOctober19,2010AUnifiedApproachforSolvingVertexPartitioningProblemsinPolynomialTime33/1smelborPgninoititraPxetreVgnivloSnegreBfoytisrevinUellehstaVnitraM,etnomleByme´RnoisulcnoCstluseremoSsnoitineddnanoitcudortnI
treVgnivloSnegreBfoytisrevinUellehstaVnitraM,etnomleByme´RFindinglargegraphclasseshavingboolean-widthO(logn).OurgoalBui-Xuan,TelleandVatshelle[’09]showedthatcertainvertexpartitioningproblemscanbesolvedinpolynomialtimeongraphshavingboolean-widthO(logn).Theseproblemsinclude:IndependentSet,DominatingSet,PerfectCode,k-Coloring,H-Cover,H-Homomorphism,MotivationnoisulcnoCstluseremoSsnoitineddnanoitcudortnI33/2smelborPgninoititraPxe
hparGe´RymeBmlnoetclasses,aMtrniaVstehlIntroductionanddefinitionsSomeresultsConclusionorderedelUybinevsrtiinclusionyfoeBgrneoSvlnigeVtrxeaPtrtioiingnrPboelsm/333