Path Problems in Networks

Path Problems in Networks

John Baras, George Theodorakopoulos
ISBN: 9781598299236 | PDF ISBN: 9781598299243
Copyright © 2010 | 77 Pages | Publication Date: 01/01/2010

BEFORE YOU ORDER: You may have Academic or Corporate access to this title. Click here to find out: 10.2200/S00245ED1V01Y201001CNT003

Ordering Options: Paperback $30.00   E-book $24.00   Paperback & E-book Combo $37.50

Why pay full price? Members receive 15% off all orders.
Learn More Here

Read Our Digital Content License Agreement (pop-up)

Purchasing Options:

The algebraic path problem is a generalization of the shortest path problem in graphs. Various instances of this abstract problem have appeared in the literature, and similar solutions have been independently discovered and rediscovered. The repeated appearance of a problem is evidence of its relevance. This book aims to help current and future researchers add this powerful tool to their arsenal, so that they can easily identify and use it in their own work. Path problems in networks can be conceptually divided into two parts: A distillation of the extensive theory behind the algebraic path problem, and an exposition of a broad range of applications. First of all, the shortest path problem is presented so as to fix terminology and concepts: existence and uniqueness of solutions, robustness to parameter changes, and centralized and distributed computation algorithms. Then, these concepts are generalized to the algebraic context of semirings. Methods for creating new semirings, useful for modeling new problems, are provided. A large part of the book is then devoted to numerous applications of the algebraic path problem, ranging from mobile network routing to BGP routing to social networks. These applications show what kind of problems can be modeled as algebraic path problems; they also serve as examples on how to go about modeling new problems.

This monograph will be useful to network researchers, engineers, and graduate students. It can be used either as an introduction to the topic, or as a quick reference to the theoretical facts, algorithms, and application examples. The theoretical background assumed for the reader is that of a graduate or advanced undergraduate student in computer science or engineering. Some familiarity with algebra and algorithms is helpful, but not necessary. Algebra, in particular, is used as a convenient and concise language to describe problems that are essentially combinatorial.

Table of Contents

Classical Shortest Path
The Algebraic Path Problem
Properties and Computation of Solutions
Related Areas
List of Semirings and Applications

About the Author(s)

John Baras, University of Maryland
John S. Baras received a B.S. in Electrical Engineering from the National Technical University of Athens, Greece, in 1970, M.S. and Ph.D. in Applied Mathematics from Harvard Univ. in 1971 and 1973. Founding Director of the Institute for Systems Research from 1985 to 1991. Since August 1973 he has been with the Electrical and Computer Engineering Department, and the Applied Mathematics Faculty, at the University of Maryland, College Park. Since 1991 Dr. Baras has been the Director of the Maryland Center for Hybrid Networks (HYNET). His many awards include the 1980 George S. Axelby Prize of the IEEE Control Systems Society and the 2007 IEEE Communications Society Leonard G. Abraham Prize in the Field of Communication Systems.Fellow of the IEEE and a Foreign Member of the Royal Swedish Academy of Engineering Sciences (IVA). He has given many invited plenary lectures at prestigious international conferences including the IEEE CDC, ECC, ECAI, Mobicom. His research interests include control, communication and computing systems.

George Theodorakopoulos
George Theodorakopoulos is a senior researcher at the Ecole Polytechnique Federale de Lausanne (EPFL), Lausanne, Switzerland. He received his Ph.D. and M.Sc. from the University of Maryland, College Park, and his B.Sc. from the National Technical University of Athens, Greece, all in Electrical and Computer Engineering, in 2007, 2004, and 2002, respectively. Half of his Ph.D. work was on the application of the algebraic path problem to trust computation. This work resulted in two awards: the best paper award at the ACM Wireless Security workshop (WiSe 2004) and the IEEE Leonard G. Abraham prize (IEEE Journal on Selected Areas in Communications 2006). His research interests also include game theory (the other half of his Ph.D.), trust and reputation systems, and network security.

Browse by Subject
ACM Books
IOP Concise Physics
0 items

Note: Registered customers go to: Your Account to subscribe.

E-Mail Address:

Your Name: