Routing, Flow, and Capacity Design in Communication and Computer Networks

APPENDIX B

Introduction to Complexity Theory and NP-Completeness

Appie van de Liefvoort,     University of Missouri–Kansas City

B.1 INTRODUCTION

It has been said that there are at least two ways to catch a fly: with honey and with vinegar. However, one of these methods is much more effective in catching a fly. Such is the story of most problems: there are several methods or algorithms for their solution and some algorithms are more efficient than others. There are a number of problems, however, where the choice of algorithm does not seem to matter much: the worst case time complexity is terrible, no matter how you turn it. This is the focus of this appendix.

In keeping with this book we use the following terminology. By the problem, we mean ...