000 03897nam a22005175i 4500
001 vtls000560450
003 RU-ToGU
005 20210922090328.0
007 cr nn 008mamaa
008 170212s2015 gw | s |||| 0|eng d
020 _a9783319212753
_9978-3-319-21275-3
024 7 _a10.1007/978-3-319-21275-3
_2doi
035 _ato000560450
040 _aSpringer
_cSpringer
_dRU-ToGU
050 4 _aQA76.9.A43
072 7 _aUMB
_2bicssc
072 7 _aCOM051300
_2bisacsh
082 0 4 _a005.1
_223
100 1 _aCygan, Marek.
_eauthor.
_9450903
245 1 0 _aParameterized Algorithms
_helectronic resource
_cby Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh.
260 _aCham :
_bSpringer International Publishing :
_bImprint: Springer,
_c2015.
300 _aXVII, 613 p. 84 illus., 25 illus. in color.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
505 0 _aIntroduction -- Kernelization -- Bounded Search Trees -- Iterative Compression -- Randomized Methods in Parameterized Algorithms -- Miscellaneous -- Treewidth -- Finding Cuts and Separators -- Advanced Kernelization Algorithms -- Algebraic Techniques: Sieves, Convolutions, and Polynomials -- Improving Dynamic Programming on Tree Decompositions -- Matroids -- Fixed-Parameter Intractability -- Lower Bounds Based on the Exponential-Time Hypothesis -- Lower Bounds for Kernelization.
520 _aThis comprehensive textbook presents a clean and coherent account of most fundamental tools and techniques in Parameterized Algorithms and is a self-contained guide to the area. The book covers many of the recent developments of the field, including application of important separators, branching based on linear programming, Cut & Count to obtain faster algorithms on tree decompositions, algorithms based on representative families of matroids, and use of the Strong Exponential Time Hypothesis. A number of older results are revisited and explained in a modern and didactic way. The book provides a toolbox of algorithmic techniques. Part I is an overview of basic techniques, each chapter discussing a certain algorithmic paradigm. The material covered in this part can be used for an introductory course on fixed-parameter tractability. Part II discusses more advanced and specialized algorithmic ideas, bringing the reader to the cutting edge of current research. Part III presents complexity results and lower bounds, giving negative evidence by way of W[1]-hardness, the Exponential Time Hypothesis, and kernelization lower bounds. All the results and concepts are introduced at a level accessible to graduate students and advanced undergraduate students. Every chapter is accompanied by exercises, many with hints, while the bibliographic notes point to original publications and related work.
650 0 _aComputer Science.
_9155490
650 0 _aAlgorithms.
_9304813
650 1 4 _aComputer Science.
_9155490
650 2 4 _aAlgorithm Analysis and Problem Complexity.
_9303732
650 2 4 _aAlgorithms.
_9304813
700 1 _aFomin, Fedor V.
_eauthor.
_9326385
700 1 _aKowalik, Łukasz.
_eauthor.
_9468040
700 1 _aLokshtanov, Daniel.
_eauthor.
_9468041
700 1 _aMarx, Dániel.
_eauthor.
_9468042
700 1 _aPilipczuk, Marcin.
_eauthor.
_9468043
700 1 _aPilipczuk, Michał.
_eauthor.
_9468044
700 1 _aSaurabh, Saket.
_eauthor.
_9468045
710 2 _aSpringerLink (Online service)
_9143950
773 0 _tSpringer eBooks
856 4 0 _uhttp://dx.doi.org/10.1007/978-3-319-21275-3
912 _aZDB-2-SCS
999 _c415550