## Analysis and Design of Algorithms for Combinatorial Problems (Google eBook)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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

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 |

### Common terms and phrases

algorithm analysis approximation algorithms asymptotic binary binary tree boolean equation 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 equivalent to H exists Extendible Hashing extension face Figure function GCRP given graph G greedy algorithm Hence hyperarc hypergraph input integer K-center problem K-subset kernel labels layout Lemma length linear local-ratio matching minimum nodes nonfree number of source obtained operations output p-random graph P—SPACE parallel parameters path planar graphs polynomial probabilistic Proc procedure processor Proof prove RAM’s random Random Access Machines recursive relation result row tree Science Publishers B.V. sequence SMT’s solved source sets step stored strands structure subgraph subset Theorem tion tracks trie tuple Turing Machine variables vertex Vertex Cover Problem vertices VLSI