國立虎尾科技大學 |

Parameterized Algorithms

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Parameterized Algorithms/ by Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh.
Author:	Cygan, Marek.
other author:	Fomin, Fedor V.
Description:	XVII, 613 p. 84 illus., 25 illus. in color.online resource. :
Contained By:	Springer Nature eBook
Subject:	Algorithms. -
Online resource:	https://doi.org/10.1007/978-3-319-21275-3
ISBN:	9783319212753

Parameterized Algorithms
Cygan, Marek.

Parameterized Algorithms[electronic resource] /by Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh. - 1st ed. 2015. - XVII, 613 p. 84 illus., 25 illus. in color.online resource.

Introduction -- 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.

This 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.

ISBN: 9783319212753

Standard No.: 10.1007/978-3-319-21275-3doiSubjects--Topical Terms:

527865
Algorithms.

LC Class. No.: QA76.9.A43

Dewey Class. No.: 005.1

Parameterized Algorithms
LDR:03314nam a22003975i 4500 001 961395
003 DE-He213
005 20200630083304.0
007 cr nn 008mamaa
008 201211s2015 gw | s |||| 0|eng d
020 $a 9783319212753 $9 978-3-319-21275-3
024 7 $a 10.1007/978-3-319-21275-3 $2 doi
035 $a 978-3-319-21275-3
050 4 $a QA76.9.A43
072 7 $a UMB $2 bicssc
072 7 $a COM051300 $2 bisacsh
072 7 $a UMB $2 thema
082 0 4 $a 005.1 $2 23
100 1 $a Cygan, Marek. $4 aut $4 http://id.loc.gov/vocabulary/relators/aut $3 1067026
245 1 0 $a Parameterized Algorithms $h [electronic resource] / $c by Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh.
250 $a 1st ed. 2015.
264 1 $a Cham : $b Springer International Publishing : $b Imprint: Springer, $c 2015.
300 $a XVII, 613 p. 84 illus., 25 illus. in color. $b online resource.
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
347 $a text file $b PDF $2 rda
505 0 $a Introduction -- 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 $a This 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 $a Algorithms. $3 527865
650 1 4 $a Algorithm Analysis and Problem Complexity. $3 593923
700 1 $a Fomin, Fedor V. $4 aut $4 http://id.loc.gov/vocabulary/relators/aut $3 792546
700 1 $a Kowalik, Łukasz. $e author. $4 aut $4 http://id.loc.gov/vocabulary/relators/aut $3 1255782
700 1 $a Lokshtanov, Daniel. $e author. $4 aut $4 http://id.loc.gov/vocabulary/relators/aut $3 1255783
700 1 $a Marx, Dániel. $e author. $4 aut $4 http://id.loc.gov/vocabulary/relators/aut $3 1255784
700 1 $a Pilipczuk, Marcin. $e author. $4 aut $4 http://id.loc.gov/vocabulary/relators/aut $3 1255785
700 1 $a Pilipczuk, Michał. $e author. $4 aut $4 http://id.loc.gov/vocabulary/relators/aut $3 1255786
700 1 $a Saurabh, Saket. $e author. $4 aut $4 http://id.loc.gov/vocabulary/relators/aut $3 1255787
710 2 $a SpringerLink (Online service) $3 593884
773 0 $t Springer Nature eBook
776 0 8 $i Printed edition: $z 9783319212746
776 0 8 $i Printed edition: $z 9783319212760
776 0 8 $i Printed edition: $z 9783319357027
856 4 0 $u https://doi.org/10.1007/978-3-319-21275-3
912 $a ZDB-2-SCS
912 $a ZDB-2-SXCS
950 $a Computer Science (SpringerNature-11645)
950 $a Computer Science (R0) (SpringerNature-43710)