Data Structures and Algorithms

Approximation Algorithms

• Geometry, Flows, and Graph-Partitioning Algorithms (CACM 2008)
  • Surveys approaches to approximate graph partitioning, mostly based on network flow and congested links.

Constraint Optimization

• A Decentralized Approach to the Art Gallery Problem (FWCG 2007)
  • Casts and solves variations of the art gallery problem as distributed constraint optimization problems.

Network and Graph Characteristics, Construction

• Emergence of Scaling in Random Networks (Science 1999)
  • Demonstrates existence of power law degree distribution in several real networks, and shows that mechanisms not based on continuous growth and preferential attachment do not result in such a system (including ER and Watts-Strogatz small world graphs)
• Classes of Small-World Networks (PNAS 2000)
  • Many real world networks actually fall into one of three classes of small-world networks: Scale-free, broad-scale, single-scale; adding aging and capacity to small-world growth models introduces distribution cutoffs seen in broad-scale and single-scale
• Emergence of Tempered Preferential Attachment from Optimization (PNAS 2007)
  • Demonstrates that real world data may be more realistically fit via a preferential attachment model including saturation and viability; shows how that model may arise from an optimization process
• Evolving Networks with Distance Preferences (PR-E 2002)
  • Looks at networks where nodes are added via a distance preference function for connecting to existing nodes; can produce power law degree distribution as in scale free construction, but differs in other characteristics such as clustering coefficient
• Generating Network Topologies That Obey Power Laws (GLOBECOM 2000)
  • Presents two algorithms for constructing graphs that closely follow observing Internet behavior.