Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Niedermeier R. — Invitation to Fixed Parameter Algorithms
Niedermeier R. — Invitation to Fixed Parameter Algorithms

Читать книгу
бесплатно

Скачать книгу с нашего сайта нельзя

Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Invitation to Fixed Parameter Algorithms

Автор: Niedermeier R.

Аннотация:

A fixed-parameter is an algorithm that provides an optimal solution to a combinatorial problem. This research-level text is an application-oriented introduction to the growing and highly topical area of the development and analysis of efficient fixed-parameter algorithms for hard problems.
The book is divided into three parts: a broad introduction that provides the general philosophy and motivation; followed by coverage of algorithmic methods developed over the years in fixed-parameter algorithmics forming the core of the book; and a discussion of the essential from parameterized hardness theory with a focus on W [1]-hardness, which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology.
Aimed at graduate and research mathematicians, programmers, algorithm designers and computer scientists, the book introduces the basic techniques and results and provides a fresh view on this highly innovative field of algorithmic research.


Язык: en

Рубрика: Computer science/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 2006

Количество страниц: 312

Добавлена в каталог: 22.05.2008

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
$P_3$      94
$\Pi_{i, j, k}$ Graph MODIFICATION      247
(n — k)-GRAPH Coloring      255
0/1-variable      68
2-CNF-Satisfiability      5
3-CNF-Satisfiability      5 208 216
3-Coloring      216
3-Hitting Set      29 72
3-Satisfiability      14 26
3-Set Packing      193
Acyclicity      136 153 271
Algorithm engineering      36 184 202 249
Algorithmic graph theory      150
Annotation      60
Annotation, refined      116
Annotation, vertex pair      95
Approximation algorithm      3 15 20 33 64 120 237
Approximation algorithm, Vertex Cover      67
Approximation polynomial-time      80
Approximation ratio      20
Approximation scheme, efficient polynomial-time      239
Approximation scheme, fully polynomial-time      21 239
Approximation scheme, polynomial-time      21 239
Approximation theory      67
APX      21
Arc annotation      262
Arc annotation, nested      263
Average-case analysis      3 15
Bag      151
Bell number      183
Betweenness      43
Biclique      121
Bidimensionality      245
Big Oh notation      18
Binary encoding      127
Binary Knapsack      126
Binomial coefficient      124
Boolean constraint      269
Boolean constraint, family      269
Bounded FPT      233
Branch decomposition      173
Branch-and-bound      120
Branching      90
Branching, algorithm      121
Branching, number      92
Branching, object      118
Branching, vector      92
Branchwidth      173 267
Capacitated graph      251
Capacitated tree      131
Capacitated vertex cover      251
Capacity      251
Case distinction      88
Case distinction, art of      94
Case distinction, complete      99
Case distinction, re-engineering of      119
Center String      43 see
Character matrix      103
Characteristic polynomial      92
Choice string      221
Chord      249
Chordal Completion      249
Clause      4
Clause, form      58
Clause, length of a      59
CLIQUE      22 45 207 213 221
Clique, disjoint union of      93
Closed under taking minors      196
Closest k-LEAF Power      250
Closest String      43 103 181
Closest Substring      44 220 241
Cluster EDITING      60 93 250
CNF-Satisfiability      4 54 205
CNF-Satisfiability, parameterizations of      5
Coding theory      103 258
color-coding      178 248 273
Coloring      164
Coloring, extension of a      162
Column isomorphism      182
Column type      182
Combinatorial explosion      2 5 12 28
Combined complexity      270
Communication problem      10
Compact description      35 39
Compatibility      261
Compatibility of UNROOTED Phylogenetic Trees      261
compiler optimization      150
Complement graph      25 207
Complementary unit clause rule      268
Compression step      185
Computational biology      84 103
Computer algebra      93
Computer-assisted analysis      98
Computers and Intractability      3 20
Condensation      134
Conflict triple      93
Conjunctive normal form      58
Connected component      19 62
Consensus problem      265
Consensus String      43 see
Consistency      163
Consistency, property      137 151
Constrained Minimum Vertex Cover      254
Constraint Bipartite Vertex Cover      44 253
Constraint satisfaction      43
Contact map      264
Context-free language, word problem      124
Convex hull      46 126
Convex position      272
Correlation Clustering      122
Crossing number      256
Crown of a graph      69
Crown, reduction      193
Crown, rule      39 256
Crown, structure      69
CYCLE      19
CYK algorithm      124
d-Hitting Set      72 101
Data clustering      60
Data complexity      270
Data disparity      259
Data reduction      8 24 31 107 188
Data reduction, by folding      84
Data reduction, crown      69
Data reduction, local      60
Data reduction, parameter-dependent      32 56 60 73
Data reduction, parameter-independent      12 32 56 68
Database      145 271
Database query      271
Database, query      270
Database, relational      270
Database, theory      266
Decision problem      6 17
Decomposition property      129
Deficiency      46 267
Deficiency, maximum      46 267
Degree of a vertex      18
Degree-branching      90 98
Demand path      10
Demand value      131
Dependence structure      164
Descriptive complexity      172 271
Dichotomy theorem      270
Dictionary look-up      145
Dijkstra algorithm      130
Dirty column      103
Distance from triviality      46 256 272
Distinguishing SUBSTRING Selection      44 241
Divide a coloring      167
Dominating set      1 26 89 157 197 207 210
Dominating Set in Planar Graphs      14 74
Dominating Set, in bipartite graphs      7
Domination      102
Domination, number      74
Double counting      35 162
Drosophila      205
Drosophila, melanogaster      4
Drug design      34 251
Dulmage — Mendelsohn decomposition      255
Dynamic programming      33 37 42 124
Edge Bipartization      249
Edge, addition      246
Edge, capacity      131
Edge, contraction      11 19
Edge, deletion      246
Edge, domination      273
Edge, editing      246
Edge, modification      60
Electrical network      228 257
Empirical confirmation      35
Enumeration      35
Error compensation      246
Euler formula      19 89 108
Evolutionary, relationship      259
Evolutionary, tree      42 259
Exact algorithm      3 5 16
Excluded grid theorem      256
Exhaustive search      88 125
Exit vertex      74
Expected running time      179
Experimental work      86
Expert system      150
Exponential time hypothesis      231
Face      155
Facility location      84
Fault coverage      253
FEEDBACK Vertex Set      176 187 247
Fill-in      154
First-order logic      170
Fixed-parameter algorithm, subexponential-time      243
Fixed-parameter intractability      205
Fixed-parameter intractability, bounded      234
Fixed-parameter intractable      22
Fixed-parameter tractability, bounded      233
Fixed-parameter tractable      22 23
Folding      72 90 146
Forbidden set characterization      246
Forbidden subgraph characterization      94 250
Forget node      153
Formal language theory      148
Formula, antimonotone      212
Formula, length of a      59
Formula, propositional      58
Formula, structure      5
Formula, t-normalized      211
Four-color theorem      32 57 81
FPT      27
FPTAS      see “Polynomial-time approximation scheme”
FPTAS, fully      21
Free variable      171
Frequency assignment      150
Gadget      77
Gadget, edge      78
Gadget, vertex      75
Gallai — Edmonds structure theorem      255
Gate Matrix Layout      172
Gene      84
Gene, expression      258
General Weighted Vertex Cover      217
Genome rearrangement      84
Genomic variation      264
Genotype      264
Genotype, matrix      264
Graph Bipartization      184 241 248
Graph coloring      45 255
Graph Minor Order Testing      27
Graph Minor Theory      27
Graph minor, closed under      27
Graph minor, theorem      196
Graph minor, theory      195
Graph modification      93 245
Graph property      246
Graph separator      153 155
Graph, $K_{3, 3}$-minor-free      245
Graph, $K_{5}$-minor-free      245
Graph, bipartite      19 45 65 256
Graph, bounded genus      245
Graph, bull      250
Graph, chordal      121 154 256
Graph, class      33
Graph, cluster      60
Graph, complete      19
Graph, complete bipartite      19
Graph, connected      19
Graph, d-regular      18
Graph, dart      250
Graph, directed      18
Graph, directed incidence      267
Graph, disk      245
Graph, display      262
Graph, edge-weighted      128
Graph, gem      250
Graph, genus      257
Graph, grid      151 172
Graph, grid-like      245
Graph, incidence      267
Graph, intersection      154
Graph, isomorphic      19
Graph, layer      156
Graph, map      245
Graph, minor      19 196
Graph, outerplanar      155
Graph, permutation      154
Graph, planar      2 19 32 243
Graph, plane      19
Graph, plane, face of a      19
Graph, primal      266
Graph, regular      99
Graph, similarity      60
Graph, simple      18
Graph, sparse      86
Graph, split      45 256
Graph, subdivision of a      19
Graph, tree-like      150
Graph, undirected      18
Graph, variable interaction      5
Greedy algorithm      194
Greedy localization      190
Greedy phase      191
Guaranteed value      42
Guard vertex      75
Hamming distance      18
Haplotype      264
Haplotype, matrix      264
Haplotyping      264
Hash table      143
Hashing      178 180
Hereditary property      246
Heuristic, method      3 15
Heuristic, strategy      35
Hitting Set      227
Hyperedge      102
Hypergraph      34 72 267
Incomplete Perfect Path Phylogeny Haplotyping      265
Independence property      125
Independent dominating set      176
Independent set      24 89 206 210 213
Independent Set in Planar Graphs      38 42 57
Individual variables      170
Information retrieval      258
1 2 3
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2019
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте