---

BISS 05 Algorithms, Chance and Networks

Links, papers, and lecture notes.

• Day 1

• Day 2

• Day 3:
  • Comparative performance evaluation of backbone formation protocols
  • Computing smallest possible dominating sets in parallel
  • Broadcasting in sensor networks
  • Device discovery and scatternet formation in BlueTooth networks

• Day 4:
  • The structure of information networks
  • Hits with its complete analysis
  • Google's beginnings

• Day 5:
  • Secure sensor networks

Errata: Exercise 2 of Day 2 concerns unit disk graphs only. It asks to show that in unit disk graphs any maximal independent set is at most 4 OPT +1, where OPT denotes the size of trhe smallest connected dominating set in the graph.

Note: The exercises to solve are those appearing in the power point presentations (Day 1 & 2). The homework must be turned in by Sunday, April 3, 2005. Instructions concerning the submission procedure will appear on this web site.

Submission procedure: Students turning in their homeworks please send it by email in PDF or postscript format by email to me, or by regular mail. Addresses can be found on my web page.

Risultati