• Article  

      A combinatorial treatment of balancing networks 

      Busch, Costas; Mavronicolas, Marios (1996)
      Balancing networks, originally introduced by Aspnes et al. (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 348-358, May 1991), represent a new class of distributed, low-contention data structures ...
    • Article  

      The impact of network structure on the stability of greedy protocols 

      Koukopoulos, D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2005)
      Some examples of the impact network structure has on stability behavior of greedy protocols and networks were presented. An important problem was to study the impact of network structure parameters on other greedy protocols. ...
    • Article  

      The price of anarchy for polynomial social cost 

      Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2006)
      In this work, we consider an interesting variant of the well studied KP model for selfish routing on parallel links, which reflects some influence from the much older Wardrop model [J.G. Wardrop, Some theoretical aspects ...
    • Article  

      Propagation in CSP and SAT 

      Dimopoulos, Yannis; Stergiou, K. (2006)
      Constraint Satisfaction Problems and Prepositional Satisfiability, are frameworks widely used to represent and solve combinatorial problems. A concept of primary importance in both frameworks is that of constraint propagation. ...
    • Conference Object  

      A randomized, O(log w)-depth 2-smoothing network 

      Mavronicolas, Marios; Sauerwald, T. (2009)
      A K-smoothing network is a distributed, low-contention data structure where tokens arrive arbitrarily on w input wires and reach w output wires via their completely asynchronous propagation through the network. The maximum ...
    • Conference Object  

      Wait-free solvability via combinatorial topology 

      Mavronicolas, Marios (1996)
      This paper addresses the question of whether Algebraic Topology is really necessary for determining the characterization of solvable tasks for the case of general t. A Combinatorial Topology framework, totally bypassing ...