000 04118nam a22004935i 4500
999 _c200434322
_d52534
003 DE-He213
005 20231104114347.0
007 cr nn 008mamaa
008 150720s2015 gw | s |||| 0|eng d
020 _a9783319212753
_z978-3-319-21275-3
024 7 _a10.1007/978-3-319-21275-3
_2doi
040 _aTR-AnTOB
_beng
_cTR-AnTOB
_erda
050 4 _aQA76.9.A43
072 7 _aUMB
_2bicssc
072 7 _aCOM051300
_2bisacsh
072 7 _aUMB
_2thema005.1
_223
100 1 _aCygan, Marek.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
245 1 0 _aParameterized Algorithms /
_cby Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh.
264 1 _aCham :
_bSpringer International Publishing :
_bImprint: Springer,
_c2015.
300 _a1 online resource
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
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 software.
650 0 _aAlgorithms.
650 1 4 _aAlgorithm Analysis and Problem Complexity.
_0http://scigraph.springernature.com/things/product-market-codes/I16021
650 2 4 _aAlgorithms.
_0http://scigraph.springernature.com/things/product-market-codes/M14018
700 1 _aFomin, Fedor V.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
700 1 _aKowalik, Łukasz.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
700 1 _aLokshtanov, Daniel.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
700 1 _aMarx, Dániel.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
700 1 _aPilipczuk, Marcin.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
700 1 _aPilipczuk, Michał.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
700 1 _aSaurabh, Saket.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
710 2 _aSpringerLink (Online service)
856 4 0 _uhttps://doi.org/10.1007/978-3-319-21275-3
_3Springer eBooks
_zOnline access link to the resource
942 _2lcc
_cEBK
041 _aeng