Analysis and Design of Algorithms for Combinatorial Problems

Front Cover
G. Ausiello, M. Lucertini
Elsevier, May 1, 1985 - Mathematics - 318 pages
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

Chapter 1 Strongly equivalent directed hypergraphs
1
Chapter 2 A localratio theorem for approximating the weighted vertex cover problem
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
Copyright

Common terms and phrases

Bibliographic information