Analysis and Design of Algorithms for Combinatorial Problems

✍ Scribed by G. Ausiello and M. Lucertini (Eds.)

• Publisher: Elsevier Science Ltd
• Year: 1985
• Tongue: English
• Leaves: 335
• Series: North-Holland Mathematics Studies 109 / Annals of Discrete Mathematics 25
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Content:
General Editor
Page ii

Edited by
Page iii

Copyright page
Page iv

Foreword
Pages v-vii
Giorgio Ausiello, Mario Lucertini

Strongly Equivalent Directed Hypergraphs Original Research Article
Pages 1-25
G. Ausiello, A. D'atri, D. Sacca'

A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem Original Research Article
Pages 27-45
R. Bar-Yehuda, S. Even

Dynamic Programming Parallel Procedures for SIMD Architectures Original Research Article
Pages 47-63
Paola Bertolazzi

Simulations Among Classes of Random Access Machines and Equivalence Among Numbers Succinctly Represented Original Research Article
Pages 65-89
A. Bertoni, G. Mauri, N. Sabadini

A Realistic Approach to VLSI Relational Database Processing Original Research Article
Pages 91-108
M.A. Bonuccelli, E. Lodi, F. Luccio, P. Maestrini, L. Pagli

On Counting Becs Original Research Article
Pages 109-124
R. Casas, J. Díaz, M. Vergés

Rigid Extensions of Graph Maps Original Research Article
Pages 125-143
I.S. Filotti

Algebraic Methods for Trie Statistics Original Research Article
Pages 145-188
Philippe Flajolet, Mireille Regnier, Dominique Sotteau

Easy Solutions for the K–Center Problem or the Dominating Set Problem on Random Graphs Original Research Article
Pages 189-209
Dorit S. Hochbaum

Network Design with Multiple Demand: A New Approach Original Research Article
Pages 211-237
M. Lucertini, G. Paletta

How to Find Long Paths Efficiently Original Research Article
Pages 239-254
B. Monien

Compact Channel Routing of Multiterminal Nets Original Research Article
Pages 255-279
M. Sarrafzadeh, F.P. Preparata

Consistency of Quadratic Boolean Equations and the König-Egerváry Property for Graphs Original Research Article
Pages 281-290
Bruno Simeone

On Some Relationships Between Combinatorics and Probabilistic Analysis Original Research Article
Pages 291-309
M. Talamo, A. Marchetti–Spaccamela, M. Protasi

A Threshold for Multiple Edge Coverings in Random Hypergraphs Original Research Article
Pages 311-319
C. Vercellis