Steiner Tree Problems In Computer Communication Networks

By: Ding-zhu Du, Xiaodong Hu

Write A Review

Hardcover | 25 February 2008

At a Glance

Hardcover
376 Pages

Dimensions(cm)
23.5 x 15.88 x 2.54

Hardcover

RRP $261.99

$235.99

10%OFF

or 4 interest-free payments of $59.00 with

Ships in 15 to 25 business days

The Steiner tree problem is one of the most important combinatorial optimization problems. It has a long history that can be traced back to the famous mathematician Fermat (1601-1665). This book studies three significant breakthroughs on the Steiner tree problem that were achieved in the 1990s, and some important applications of Steiner tree problems in computer communication networks researched in the past fifteen years. It not only covers some of the most recent developments in Steiner tree problems, but also discusses various combinatorial optimization methods, thus providing a balance between theory and practice.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $79.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Mathematics Combinatorics & Graph Theory Computing & I.T.Computer Networking & Communications Engineering & Technology Technology in General Engineering in General Optimisation Computer Science Systems Analysis & Design Mathematical Theory of Computation

Booktopia Publisher Services World Scientific Publishing

Preface	p. v
Fundamentals of Classical Steiner Tree Problem
Minimax Approach and Steiner Ratio	p. 1
Minimax Approach	p. 3
Chebyshev Theorem	p. 4
Du-Hwang Theorem	p. 6
Geometric Inequalities	p. 10
Analysis of Approximation Performance	p. 13
Steiner Ratio in the Euclidean Plane	p. 14
Equivalent Minimax Problem	p. 15
Characteristic Area	p. 17
Inner Spanning Trees	p. 20
Critical Structure	p. 25
Hexagonal Trees	p. 29
Steiner Ratios in Other Metric Spaces	p. 34
Steiner Ratios in Euclidean Spaces	p. 34
Steiner Ratio in Rectilinear Spaces	p. 36
Steiner Ratio in Banach Spaces	p. 37
Discussions	p. 38
k-Steiner Ratios and Better Approximation Algorithms	p. 41
k-Steiner Ratio	p. 43
Upper Bound for k-Steiner Ratio	p. 44
Lower Bound for k-Steiner Ratio	p. 52
Approximations Better Than Minimum Spanning Tree	p. 59
Greedy Strategy	p. 61
Variable Metric Method	p. 70
Relative Greedy Strategy	p. 72
Preprocessing Technique	p. 73
Loss-Contracting Algorithm	p. 74
Discussions	p. 76
Geometric Partitions and Polynomial Time Approximation Schemes	p. 79
Guillotine Cut for Rectangular Partition	p. 80
1-Guillotine Cut	p. 85
m-Guillotine Cut	p. 88
Guillotine Cut for Rectilinear Steiner Minimum Tree	p. 90
Portals	p. 93
Portals for Rectilinear Steiner Minimum Tree	p. 94
Portals versus Guillotine Cuts	p. 97
Portals Integrated with Guillotine Cuts	p. 99
Two-Stage Portals	p. 104
Banyan and Spanner	p. 106
Discussions	p. 108
Grade of Service Steiner Tree Problem	p. 111
GoSST Problem in the Euclidean Plane	p. 114
Recursive Approximation Algorithm	p. 114
Branch-and-Bound Algorithm	p. 123
Minimum GoSST Problem in Graphs	p. 128
[beta]-Convex [alpha]-Approximation Steiner Tree Algorithms	p. 129
Algorithm for Two Non-Zero Rates	p. 132
Algorithm for Arbitrary Number of Rates	p. 135
Discussions	p. 137
Steiner Tree Problem for Minimal Steiner Points	p. 141
In the Euclidean Plane	p. 142
Complexity Study	p. 144
Steinerized Minimum Spanning Tree Algorithm	p. 146
Greedy Algorithm	p. 151
Polynomial Time Approximation Scheme	p. 155
Partition Strategy	p. 157
Approximation Scheme	p. 157
Exact Algorithm	p. 160
Connecting Local Forests and Boundary Points	p. 161
In the Rectilinear Plane	p. 162
Steinerized Minimum Spanning Tree Algorithm	p. 166
Greedy Algorithm	p. 170
In Metric Spaces	p. 172
Discussions	p. 175
Bottleneck Steiner Tree Problem	p. 177
Complexity Study	p. 178
Steinerized Minimum Spanning Tree Algorithm	p. 180
3-Restricted Steiner Tree Algorithm	p. 185
Discussions	p. 193
Steiner k-Tree and k-Path Routing Problems	p. 195
Problem Formulation and Complexity Study	p. 196
Problem Formulation	p. 196
Complexity Study	p. 198
Algorithms for k-Path Routing Problem	p. 203
Steiner Tree Based Algorithm	p. 203
Set Cover Based Algorithm	p. 208
Algorithms for k-Tree Routing Problem	p. 210
Hamilton Circuit Based Algorithm	p. 210
Steiner Tree Based Algorithm	p. 212
Discussions	p. 216
Steiner Tree Coloring Problem	p. 221
Maximum Tree Coloring	p. 222
Problem Formulation	p. 222
Inapproximability Analysis	p. 224
Approximation Algorithms	p. 229
For General Graphs	p. 229
For Special Graphs	p. 233
Minimum Tree Coloring	p. 235
Problem Formulation	p. 235
Inapproximability Analysis	p. 236
Approximation Algorithms	p. 241
For General Graphs	p. 242
For Special graphs	p. 247
Discussions	p. 250
Steiner Tree Scheduling Problem	p. 253
Minimum Aggregation Time	p. 255
Problem Formulation	p. 255
Complexity Analysis	p. 257
Greedy Algorithms	p. 263
Basic Algorithm	p. 264
Algorithms for Special Cases	p. 268
Partition Algorithm	p. 271
Aggregation Tree Construction	p. 271
Aggregation Time Schedule	p. 273
Performance Analysis of Algorithm	p. 274
Minimum Multicast Time Problem	p. 276
Problem Formulation	p. 276
Complexity Study	p. 278
Approximation Algorithm	p. 279
Performance Analysis of Algorithm	p. 282
Discussions	p. 283
Convergecast	p. 283
Multicast	p. 284
Convergecast and Multicast	p. 286
Survivable Steiner Network Problem	p. 287
Minimum k-Connected Steiner Networks	p. 289
Minimum Strong k-Connected Steiner Networks	p. 291
Minimum Weak k-Connected Steiner Networks	p. 295
Minimum Weak Two-Connected Steiner Networks	p. 296
Complexity Study	p. 299
Generalized Steiner Ratio	p. 301
In the Rectilinear Plane	p. 311
Minimum Weak Three-Edge-Connected Steiner Networks	p. 313
In the Euclidean Plane	p. 313
In the Rectilinear Plane	p. 323
Discussions	p. 325
Minimally k-Edge Connected Networks	p. 325
Minimum k-Edge Connected Spanning Networks	p. 326
Minimum k-Vertex Connected Spanning Networks	p. 328
Minimum Spanning Network of Nonuniform Connectivity	p. 330
More Steiner Tree Related Problems	p. 331
Bibliography	p. 337
Index	p. 355
Table of Contents provided by Ingram. All Rights Reserved.

Steiner Tree Problems In Computer Communication Networks

At a Glance

Hardcover

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Computer Networking & Communications

Grey Area

Dark Web Data Collection and the Future of OSINT

Liars and Outliers

Enabling the Trust that Society Needs to Thrive

The E-Myth Revisited

Why Most Small Businesses Don't Work and What to Do About It

Dark Wire

The Incredible True Story of the Largest Sting Operation Ever

Product-Focused Software Process Improvement

26th International Conference, PROFES 2025, Salerno, Italy, December 1-3, 2025, Proceedings

Hacking For Dummies

For Dummies (Computer/Tech)

Dark Wire

The Incredible True Story of the Largest Sting Operation Ever

Cybersecurity All-in-One For Dummies

For Dummies

Essentials of Computer Networking

Theory and Applications of Error Correcting Codes

Fundamentals of Software Architecture

A Modern Engineering Approach

Making Embedded Systems

2nd Edition - Design Patterns for Great Software

Linux All-In-One For Dummies

For Dummies (Computer/Tech)

Tech-Smart Parenting

How to keep your kids happy and safe online

The New Age of Sexism

How the AI Revolution is Reinventing Misogyny

Computer Networking, Global Edition

8th edition

Data Strategy

How to Use Data and Artificial Intelligence to Transform Your Business

The Site Reliability Workbook

Practical ways to implement SRE

Network Programmability and Automation

2nd Edition - Skills for the Next-Generation Network Engineer

Password Logbook (Hip Floral)

Keep Track of Usernames, Passwords, Web Addresses in One Easy and Organized Location

Keanu Reeves Is Not In Love With You

The Murky World of Online Romance Fraud

From Chaos to Clarity

How Data Visualization can Save the World

ISC2 CISSP Certified Information Systems Security Professional Official Study Guide & Practice Tests Bundle

Sybex Study Guide

Cloud Computing

2nd Edition - Concepts, Technology, Security, and Architecture

This product is categorised by