This book constitutes the refereed proceedings of the 12th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2005, held in Mont Saint-Michel, France in May 2005.The 22 revised full papers presented were carefully reviewed and selected from 48 submissions. The papers address issues such as topics in distributed and parallel computing, information dissemination, communication complexity, interconnection networks, high speed networks, wireless networking, mobile computing, optical computing, and related areas.