Analysis and Design of Algorithms for Combinatorial ProblemsG. Ausiello, M. Lucertini Combinatorial problems have been from the very beginning part of the history of mathematics. By the Sixties, the main classes of combinatorial problems had been defined. During that decade, a great number of research contributions in graph theory had been produced, which laid the foundations for most of the research in graph optimization in the following years. During the Seventies, a large number of special purpose models were developed. The impressive growth of this field since has been strongly determined by the demand of applications and influenced by the technological increases in computing power and the availability of data and software. The availability of such basic tools has led to the feasibility of the exact or well approximate solution of large scale realistic combinatorial optimization problems and has created a number of new combinatorial problems. |
Contents
1 | |
27 | |
Chapter 3 Dynamic programming parallel procedures for SIMD architectures | 47 |
Chapter 4 Simulations among classes of random access machines and equivalence among numbers succinctly represented | 65 |
Chapter 5 A realistic approach to VLSI relational database processing | 91 |
Chapter 6 On counting BECS | 109 |
Chapter 7 Rigid extensions of graph maps | 125 |
Chapter 8 Algebraic methods for trie statistics | 145 |
Chapter 9 Easy solutions for the Kcenter problem or the dominating set problem on random graphs | 189 |
a new approach | 211 |
Chapter 11 How to find long paths efficiently | 239 |
Chapter 12 Compact channel routing of multiterminal nets | 255 |
Chapter 13 Consistency of quadratic boolean equations and the KönigEgerváry property for graphs | 281 |
Chapter 14 On some relationships between combinatorics and probabilistic analysis | 291 |
Chapter 15 A threshold for multiple edge coverings in random hypergraphs | 311 |
Common terms and phrases
approximation algorithms asymptotic binary boolean equation bound bridge cardinality closure column combinatorial complexity compute connected consider contains corresponding decision problem defined definition demand vector denote dominating set problem dynamic programming edge elements embedding enumeration problems exists Extendible Hashing extension face Figure finite function GCRP given graph G greedy algorithm H and H Hence hyperarc hypergraph input integer K-center problem K-subset kernel labels layout Lemma linear local-ratio matching minimum nodes NP-complete number of source obtained operations output p-random graph P-SPACE parallel parameters planar graphs polynomial probabilistic procedure processor Proof prove Publishers B.V. North-Holland random Random Access Machines recursive relation result row tree Science Publishers B.V. sequence SMT's solved source sets step structure subgraph subset Theorem tion tracks trie tuple Turing Machine V(sh variables vertex Vertex Cover Problem vertices