0

NETWORKING AN INTERNATIONAL JOURNAL

JANUARY 1999 VOLUME 33, NUMBER 1

Contents

Balanced Network Flows. 1. A Unifying Framework for Design and Analysis of Matching Algorithms 1 C. Fremuth-Paeger and D. Jungnickel

Balanced Network Flows. II. Simple Augmentation Algorithms 29 C. Fremuth-Paeger and D. Jungnickel

Balanced Network Flows. III. Strongly Polynomial Augmentation Algorithms 43 C. Fremuth-Paeger and D. Jungnickel

Minimum-Cost Strong Network Orientation Problems: Classification, Complexity) and Algorithms 57 P. E. Burkard, K. Feldbacher, B. Klinz, and G. J. Woegi nger

Small Congestion Embedding of Graphs into Hypercubes 71 A. Matsubayashi and S. Ueno

___________________________________


NETWORKS: AN INTERNATIONAL JOURNAL

VOLUME 33, NUMBER 2, MARCH 1999

Contents

Multicriteria Network Location Problems with Sum Objectives 79
H. W. Hamacher, M. Labbe, and S. Nickel

Dynamic Multi-Sector, Multi-Instrument Financial Networks with Futures: Modeling
and Computation , 93
A. Nagumey and S. Siokos

A Dual-Ascent Procedure for the File Allocation and Join Site Selection Problem on a
Telecommunications Network 109
/. Murthy and P. K. Seo

Rectilinear Full Steiner Tree Generation 125
M. Zachariasen

A Polynomial Time Algorithm for Rectilinear Steiner Trees with Terminals Constrained
to Curves 145
M. Brazil, D. A. Thomas, and J. F. Weng

Super Edge Connectivity Properties of Connected Edge Symmetric Graphs 157
Q. U and Q. U

___________________________________


NETWORKS

VOLUME 33, NOUMBER 3, MAY 1999

Contents

On Diameter of Permutation Graphs 161
W. Gu

Transmissions in a Network with Capacities and Delays 167
D. Kagaris, G. E. Pantziou, S. Tragoudas, and C. D. Zaroliagis

Pseudo-Gilbert-Steiner Trees 175
D. Trietsch and J. F. Weng

Ail-to-AII Communication for Some Wavelength-Routed All-Optical Networks 179
B. Beauquier
A NOTE on the Bottleneck Graph Partition Problem 189
B. Kfinz and G. J. Woeginger

An Expert System for Coherent Assessment of Probabilities in Multigraph Models 193
E. Castiflo, A. S. Hadi, F. Jubete, and C. Solares

The Probabilistic Longest Path Problem 207
C. Murat and V. Th. Paschos

Congestion-Free, Dilation-2 Embedding of Complete Binary Trees into Star Graphs 221
Y.-C. Tseng, Y.-S. Chen, T.-Y. Juang, and C.-J. Chang

Various Results on the Toughness of Graphs 233
H. Broersma, E. Engbers, and H. Trommel

Multidimensional Assortment Problem with an Application 239
A. Tripathy, H. SOral, and Y. Gerchak

___________________________________

NETWORKS
AN INTERNATIONAL JOURNAL
VOLUME: 33, NUMBER: 4, JULY 1999

Contents
Special Issue: Selected Papers from DIMACS Workshop
On Switching Networks, Held July 7-9, 1997

Foreword: The DIMACS Workshop - 247
D.-Z. Du

Upper and Lower Bounds for the Average-Case Complexity of Path-Search 249
N. Pippenger

Characterizing Bit Permutation Networks 261
G. J. Chang, F. K. Hwang, and L.-D. Tong

Extended Generalized Shuffle Networks: Sufficient Conditions for Strictly
Nonblocking Operation 269
G. W. Richards and F. K. Hwang

Strictly Nonblocking Conference Networks Using High-Dimensional Meshes 293
Y. Du and G. M. Masson

Author Index to Volume 33 311

Subject Index to Volume 33 313

Volume Contents

____________________________________



NETWORKS
VOLUME 34, NUMBER 1, AUGUST 1999

Contents

Deferred-Query: An Efficient Approach for Some Problems on Interval Graphs 1
M.-S.Chang,S.-L.Peng,anäJ.-L.Liaw

On the Memory Overhead of Distributed Snapshots 11
L. Shabtay and A. Segall

Path Problems in Networks with Vector-Valued Edge Weights 19
G. K. Tay't, D. J. Rosenkrantz, and S. S. Ravi

Lower Bounds for Linear Interval Routing 37
T. Eilam, S. Moran, and S. Zaks

Deadlock-Free Interval Routing Schemes 47
M. Flammini

Optimal Edge Coloring of Large Graphs 61
J. Gornez and M. Escudero

An Optimal Algorithm for Layered Wheel Floorplan Designs 67
P. D. Kulasinghe and S. Bettayeb

A Competitive Analysis for Retransmission Timeout 73
S. Dolev, M. Kate, and J. L. Welch

____________________________________

NETWORKS
VOLUME 34, NUMBER 2, SEPTEMBER 1999


Contents


Optimal Tree 3-Sparmers in Directed Path Graphs 81
H.-O. Le and V. B. Le



An Efficient Implementation of an Algorithm for Finding K Shortest Simple Paths 88
E. Hadjiconstantinou and N. Christofides



Analysis of LP Reiaxations for Multiway and Multicut Problems 102
D. Bertsimas, C.-P. Teo, and R. Vohra




Eccentric Graphs 115
G. Chartrand, W. Gu, M. Schultz, and S. I Winters


Optimum Requirement Spanning Trees and Reliability of Tree Networks 122
T. Anazawa, T. Kodera, and M. Jimbo


On a Condition for Obtaining an Explicit Solution of Optimum Requirement Spanning
Tree 132
T, Anazawa



Greedy Online Algorithms for Routing Permanent Virtual Circuits 136
J. T. Havill and W. Mao



New Large Graphs with Given Degree and Diameter Six 154
J. Gornez, L Pelayo, and C. Balbuena



A Tabu Search Heuristic for the Steiner Tree Problem 162
M. Gendreau, J.-F. Larochelle, and B. Sanso

____________________________________