Clark School Home UMD

ISR News Story

Baras, Theodorakopoulos Publish New Book on Path Problems in Networks


Professor John S. Baras (ECE/ISR), and alumnus George Theodorakopoulos (ECE/ISR), a senior researcher at the École Polytechnique Fédérale de Lausanne (EPFL), have published a new book titled “Path Problems in Networks.”

The book is part of Morgan & Claypool’s Synthesis Lectures on Communication Networks, under the Editorship of Professor Jean Walrand of the University of California, Berkeley. This is an ongoing series of 50- to 100-page publications on topics related to the design, implementation, and management of communication networks. Each lecture is a self-contained presentation of one topic by a leading expert. The topics range from algorithms to hardware implementations and cover a broad spectrum of issues, from security to multiple-access protocols. The series addresses technologies from sensor networks to reconfigurable optical networks.

The monograph provides a modern view on the algebraic path problem, which 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, 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.

The monograph is available for free electronically for Synthesis licensing institutions (including the University of Maryland) from the web site at:
http://dx.doi.org/10.2200/S00245ED1V01Y201001CNT003

Print copies can be obtained from the Amazon website.

September 8, 2010


Prev   Next

 

 

Current Headlines

Tsiropoulou to join University of New Mexico faculty

Qu Gives Keynote at WOCC 2017

Wood filter removes toxic dye from water

Prof. Alireza Khaligh to receive Outstanding Young Alumnus Award from Illinois Tech

Simon is co-editor of new Springer auditory research book

New Class Inducted into Order of the Engineer

Northrop Grumman renews as an ISR associate partner for third consecutive year

Students of Khaligh, Wu win China Scholarship Council awards

ECE Graduate Student Team, led by Prof. Khaligh, Wins 3rd place in the Allegheny Region Cleantech University Prize (CUP) Collegiate Competition 

Paley, Abshire, Martins promoted to full Professor by UMD President Wallace Loh

News Resources

Return to Newsroom

Search News

Archived News

Events Resources

Events Calendar