On degree constrained shortest paths

Samir Khuller*, Kwangil Lee, Mark Shayman

*Corresponding author for this work

Research output: Contribution to journalConference article

4 Scopus citations

Abstract

Traditional shortest path problems play a central role in both the design and use of communication networks and have been studied extensively. In this work, we consider a variant of the shortest path problem. The network has two kinds of edges, "actual" edges and "potential" edges. In addition, each vertex has a degree/interface constraint. We wish to compute a shortest path in the graph that maintains feasibility when we convert the potential edges on the shortest path to actual edges. The central difficulty is when a node has only one free interface, and the unconstrained shortest path chooses two potential edges incident on this node. We first show that this problem can be solved in polynomial time by reducing it to the minimum weighted perfect matching problem. The number of steps taken by this algorithm is O(|E|2 log |E|) for the single-source single-destination case. In other words, for each v we compute the shortest path Pv such that converting the potential edges on Pv to actual edges, does not violate any degree constraint. We then develop more efficient algorithms by extending Dijkstra's shortest path algorithm. The number of steps taken by the latter algorithm is O(|E||V|), even for the single-source all destination case.

Original languageEnglish (US)
Pages (from-to)259-270
Number of pages12
JournalLecture Notes in Computer Science
Volume3669
DOIs
StatePublished - 2005
Event13th Annual European Symposium on Algorithms, ESA 2005 - Palma de Mallorca, Spain
Duration: Oct 3 2005Oct 6 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On degree constrained shortest paths'. Together they form a unique fingerprint.

  • Cite this