Network optimization

Samir Khuller*, Balaji Raghavachari

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

Many real-life problems can be modeled as optimization problems in networks. Examples include finding shortest paths, scheduling classes in classrooms, and finding the vulnerability of networks to disconnection because of link and node failures. In this chapter, a number of interesting problems and their algorithms are surveyed. Some of the problems studied are matching, weighted matching, maximum flow in networks, blocking flows, minimum cuts, densest subgraphs, minimum-cost flows, multi-commodity flows, minimum spanning trees, spanners, Light approximate shortest path trees, and graph coloring. Some interesting applications of matching, namely, two processor scheduling, edge covers, and the Chinese postman problem, are also discussed.

Original languageEnglish (US)
Title of host publicationHandbook of Combinatorial Optimization
PublisherSpringer New York
Pages1989-2026
Number of pages38
Volume3-5
ISBN (Electronic)9781441979971
ISBN (Print)9781441979964
DOIs
StatePublished - Jan 1 2013

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Network optimization'. Together they form a unique fingerprint.

  • Cite this

    Khuller, S., & Raghavachari, B. (2013). Network optimization. In Handbook of Combinatorial Optimization (Vol. 3-5, pp. 1989-2026). Springer New York. https://doi.org/10.1007/978-1-4419-7997-1_10