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.
Author(s): G. Ausiello and M. Lucertini (Eds.)
Series: North-Holland Mathematics Studies 109 / Annals of Discrete Mathematics 25
Publisher: Elsevier Science Ltd
Year: 1985
Language: English
Pages: ii-vii, 1-319
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
