| Description |
1 online resource : text file, PDF. |
| Series |
Chapman & Hall/CRC Applied Algorithms and Data Structures series |
|
Chapman & Hall/CRC applied algorithms and data structures series.
|
| Bibliography |
Includes bibliographical references and index. |
| Contents |
And Bibliographic Notes appear at the end of each chapter in this section. NP-Completeness and Beyond ; NP-Completeness ; A practical approach to complexity theory; Problem classes; NP-complete problems and reduction theory; Examples of NP-complete problems and reductions; Importance of problem definition; Strong NP-completeness; Why does it matter? Exercises on NP-Completeness; Easy reductions; About graph coloring; Scheduling problems; More involved reductions; 2-PARTITION is NP-complete Beyond NP-Completeness ; Approximation results; Polynomial problem instances; Linear programming; Randomized algorithms; Branch-and-bound and backtracking Exercises Going beyond NP-Completeness ; Approximation results; Dealing with NP-complete problems Reasoning on Problem Complexity ; Reasoning to Assess a Problem Complexity ; Basic |
|
Reasoning; Set of problems with polynomial-time algorithms; Set of NP-complete problems Chains-on-Chains Partitioning ; Optimal algorithms for homogeneous resources; Variants of the problem; Extension to a clique of heterogeneous resources; Conclusion Replica Placement in Tree Networks ; Access policies; Complexity results; Variants of the replica placement problem; Conclusion Packet Routing ; MEDP: Maximum edge-disjoint paths; PRVP: Packet routing with variable-paths; Conclusion Matrix Product, or Tiling the Unit Square ; Problem motivation; NP-completeness; A guaranteed heuristic; Related problems Online Scheduling ; Flow time optimization; Competitive analysis; Makespan optimization; Conclusion Bibliography Index |
| Subject |
Computer algorithms.
|
|
Computational complexity.
|
|
Algorithms.
|
|
Algorithmes. |
|
Complexité de calcul (Informatique) |
|
algorithms. |
|
Algorithms |
|
Computational complexity |
|
Computer algorithms |
| Added Author |
Robert, Yves, 1958 September 5- author.
|
|
Vivien, Frédéric, author.
|
| Other Form: |
Print version: 9781439825648 1439825645 |
| ISBN |
9781439898130 (electronic bk.) |
|
1439898138 (electronic bk.) |
|
More Resources