000 03201nam a22003855i 4500
001 294028
003 MX-SnUAN
005 20160429155129.0
007 cr nn 008mamaa
008 150903s2006 gw | o |||| 0|eng d
020 _a9783540299530
_99783540299530
024 7 _a10.1007/354029953-X
_2doi
035 _avtls000347389
039 9 _a201509030435
_bVLOAD
_c201404121418
_dVLOAD
_c201404091155
_dVLOAD
_y201402070930
_zstaff
040 _aMX-SnUAN
_bspa
_cMX-SnUAN
_erda
050 4 _aQA76.9.A43
100 1 _aFlum, Jörg.
_eautor
_9327222
245 1 0 _aParameterized Complexity Theory /
_cby Jörg Flum, Martin Grohe.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c2006.
300 _axiii, 493 páginas 51 ilustraciones
_brecurso en línea.
336 _atexto
_btxt
_2rdacontent
337 _acomputadora
_bc
_2rdamedia
338 _arecurso en línea
_bcr
_2rdacarrier
347 _aarchivo de texto
_bPDF
_2rda
490 0 _aTexts in Theoretical Computer Science. An EATCS Series
500 _aSpringer eBooks
505 0 _aFixed-Parameter Tractability -- Reductions and Parameterized Intractability -- The Class W[P] -- Logic and Complexity -- Two Fundamental Hierarchies -- The First Level of the Hierarchies -- The W-Hierarchy -- The A-Hierarchy -- Kernelization and Linear Programming Techniques -- The Automata-Theoretic Approach -- Tree Width -- Planarity and Bounded Local Tree Width -- Homomorphisms and Embeddings -- Parameterized Counting Problems -- Bounded Fixed-Parameter Tractability and Limited Nondeterminism -- Subexponential Fixed-Parameter Tractability.
520 _aParameterized complexity theory is a recent branch of computational complexity theory that provides a framework for a refined analysis of hard algorithmic problems. The central notion of the theory, fixed-parameter tractability, has led to the development of various new algorithmic techniques and a whole new theory of intractability. This book is a state-of-the-art introduction to both algorithmic techniques for fixed-parameter tractability and the structural theory of parameterized complexity classes, and it presents detailed proofs of recent advanced results that have not appeared in book form before. Several chapters are each devoted to intractability, algorithmic techniques for designing fixed-parameter tractable algorithms, and bounded fixed-parameter tractability and subexponential time complexity. The treatment is comprehensive, and the reader is supported with exercises, notes, a detailed index, and some background on complexity theory and logic. The book will be of interest to computer scientists, mathematicians and graduate students engaged with algorithms and problem complexity.
590 _aPara consulta fuera de la UANL se requiere clave de acceso remoto.
700 1 _aGrohe, Martin.
_eautor
_9327223
710 2 _aSpringerLink (Servicio en línea)
_9299170
776 0 8 _iEdición impresa:
_z9783540299523
856 4 0 _uhttp://remoto.dgb.uanl.mx/login?url=http://dx.doi.org/10.1007/3-540-29953-X
_zConectar a Springer E-Books (Para consulta externa se requiere previa autentificación en Biblioteca Digital UANL)
942 _c14
999 _c294028
_d294028