Browsing by Subject "Polynomial-time"

Now showing items 1-4 of 4

    • Article  

      Direct routing: Algorithms and complexity 

      Busch, Costas; Magdon-Ismail, M.; Mavronicolas, Marios; Spirakis, Paul G. (2004)
      Direct routing is the special case of bufferless routing where N packets, once injected into the network, must be routed along specific paths to their destinations without conflicts. We give a general treatment of three ...
    • Article  

      A new model for selfish routing 

      Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M. (2008)
      In this work, we introduce and study a new, potentially rich model for selfish routing over non-cooperative networks, as an interesting hybridization of the two prevailing such models, namely the KPmodel [E. Koutsoupias, ...
    • Conference Object  

      The power of the defender 

      Gelastou, Marina; Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Philippou, Anna; Spirakis, Paul G. (2006)
      We consider a security problem on a distributed network. We assume a network whose nodes are vulnerable to infection by threats (e.g. viruses), the attackers. A system security software, the defender, is available in the ...
    • Article  

      The price of defense and fractional matchings 

      Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Persiano, Giuseppe; Philippou, Anna; Spirakis, Paul G. (2006)
      Consider a network vulnerable to security attacks and equipped with defense mechanisms. How much is the loss in the provided security guarantees due to the selfish nature of attacks and defenses? The Price of Defense was ...