Asymptotics of Canonical and Saturated RNA Secondary Structures (2009)
Clote, Peter, Kranakis, Evangelos, Krizanc, Danny, Salvy, Bruno
It is a classical result of Stein and Waterman that the asymptotic number of RNA secondary structures is $1.104366 n^{-3/2} 2.618034^n$. In this paper, we study combinatorial asymptotics for two...
Games on Triangulations (2009)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Abstract. We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games—constructing, transforming, and marking...
Geometric Games on Triangulations Extended Abstract (2009)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Let S be a set of n points in the plane, which we assume to be in general position, i.e., no three points of S lie on the same line. A triangulation of S is a simplicial decomposition of its convex...
Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Anup Patnaik, Sunil Shende
with uncertainty in the position of the destination
Geometric Games on Triangulations Extended Abstract (2009)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
1 Introduction Let S be a set of n points in the plane, which we assume to be in general position, i.e., no threepoints of S lie on the same line. A triangulation of S is a simplicial decomposition...
Algorithms for Packing Two Circles in a Convex Polygon (2009)
Prosenjit Bose, Jurek Czyzowicz, Evangelos Kranakis, Anil Maheshwari
3
Asymptotics of Canonical and Saturated RNA Secondary Structures (2009)
Clote, Peter, Kranakis, Evangelos, Krizanc, Danny, Salvy, Bruno
It is a classical result of Stein and Waterman that the asymptotic number of RNA secondary structures is $1.104366 n^{-3/2} 2.618034^n$. In this paper, we study combinatorial asymptotics for two...
Asymptotics of Canonical and Saturated RNA Secondary Structures (2009)
Clote, Peter, Kranakis, Evangelos, Krizanc, Danny, Salvy, Bruno
It is a classical result of Stein and Waterman that the asymptotic number of RNA secondary structures is $1.104366 n^{-3/2} 2.618034^n$. In this paper, we study combinatorial asymptotics for two...
Evangelos Kranakis, Danny Krizanc, Euripides Markou
agent rendezvous in a synchronous torus
Cutting Circles into Equal Area Pieces 1 Prosenjit Bose (2008)
Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Jurek Czyzowicz
We study several problems related to cutting circles into equal area pieces. Our objective is to minimize the total length of the cuts.
Securing the Destination-Sequenced Distance Vector Routing Protocol (S-DSDV) (2008)
Tao Wan, Evangelos Kranakis, P. C. Oorschot
Abstract. A mobile ad hoc network (MANET) is formed by a group of mobile wireless nodes, each of which functions as a router and agrees to forward packets for others. Many routing protocols (e.g.,...
Online Routing in Quasi-Planar and Quasi-Polyhedral Graphs (2008)
Evangelos Kranakis, Tim Mott, Ladislav Stacho
We address the problem of online route discovery for a class of graphs that can be embedded either in two or in three dimensional space. In two dimensions we propose the class of quasi-planar graphs...
Tracking Darkports for Network Defense (2008)
David Whyte, Paul C. Oorschot, Evangelos Kranakis
We exploit for defensive purposes the concept of darkports – the unused ports on active systems. We are particularly interested in such ports which transition to become active (i.e. become...
LOCAL PTAS FOR DOMINATING AND CONNECTED DOMINATING SET IN LOCATION AWARE UDGS (2008)
Andreas Wiese, Evangelos Kranakis
Abstract. We present local 1+ɛ approximation algorithms for the minimum dominating and the connected dominating set problems in location aware Unit Disk Graphs (UDGs). Our algorithms are local in...
Playing with Triangulations (2008)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Abstract. We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games: constructing, transforming, and marking...
Abstract Exposure Maps: Removing Reliance on Attribution During Scan Detection (2008)
David Whyte, P. C. Oorschot, Evangelos Kranakis
Current scanning detection algorithms are based on an underlying assumption that scanning activity can be attributed to a meaningful specific source (i.e. the root cause or scan controller)....
Geometric Games on Triangulations Extended Abstract (2008)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Let S be a set of n points in the plane, which we assume to be in general position, i.e., no three points of S lie on the same line. A triangulation of S is a simplicial decomposition of its convex...
Running Title: “Structural RNA has lower energy than random RNA” (2008)
Peter Clote, Fabrizio Ferré, Evangelos Kranakis, Danny Krizanc
Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency
Strategies for Service Discovery over Ad Hoc Networks (2008)
Michel Barbeau, Evangelos Kranakis, Honghui Luo
Service discovery is an important and necessary component of ad hoc networks. To fit within the context of such networks, a post-query model with several service discovery strategies (named...
Balancing Traffic Load Using One-Turn Rectilinear Routing (2008)
Stephane Durocher, Evangelos Kranakis, Danny Krizanc, Lata Narayanan
Abstract. We consider the problem of load-balanced routing, where a dense network is modelled by a continuous square region and the origins and destinations correspond to pairs of points in that...
Distributed Computing on Oriented Anonymous Hypercubes with Faulty Components ∗ (2008)
Evangelos Kranakis, Nicola Santoro
We give efficient algorithms for distributed computation on anonymous, labeled, asynchronous oriented hypercubes with possible faulty components (i.e. processors and links) and deterministic...
Amos Israeli, Danny Krizanc, Evangelos Kranakis, Nicola Santoro
A set of anonymous processors is interconnected forming a complete synchronous network with sense of direction. Weak unison is the problem where all processors want to enter the same state (in our...
On the falsepositive rate of Bloom filters (2008)
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, ...
Abstract. Bloom filters are a randomized data structure for membership queries dating back to 1970. Bloom filters sometimes give erroneous answers to queries, called false positives. Bloom analyzed...
Extended Abstract, Evangelos Kranakis, Danny Krizanc
Abstract We consider the problem of searching for an item in a distributed network in the presence of uncertainty. Although the location of the item in the network is unknown information about its...
Jurek Czyzowicz, Evangelos Kranakis, Jorge Urrutia
We study a problem of dissecting a rectangle into a minimum number of pieces which may be reassembled into a square. The dissection is made using only rectilinear glass-cuts, i.e., vertical or...
On Tilable Orthogonal Polygons ∗ (2008)
György Csizmadia, Jurek Czyzowicz, Evangelos Kranakis, Eduardo Rivera-campo, Jorge Urrutia
We consider rectangular tilings of orthogonal polygons with vertices located at integer lattice points. Let G be a set of reals closed under the usual addition operation. A G-rectangle is a rectangle...
Tracking Darkports for Network Defense (2008)
David Whyte, P. C. Oorschot, Evangelos Kranakis
We exploit for defensive purposes the concept of darkports – the unused ports on active systems. We are particularly interested in such ports which transition to become active (i.e., become...
Securing the Destination-Sequenced Distance Vector Routing Protocol (S-DSDV) ⋆ (2008)
Tao Wan, Evangelos Kranakis, P. C. Oorschot
Abstract. A mobile ad hoc network (MANET) is formed by a group of mobile wireless nodes, each of which functions as a router and agrees to forward packets for others. Many routing protocols (e.g.,...
Abstract Exposure Maps: Removing Reliance on Attribution During Scan Detection (2008)
David Whyte, P. C. Oorschot, Evangelos Kranakis
Current scanning detection algorithms are based on an underlying assumption that scanning activity can be attributed to a meaningful specific source (i.e. the root cause or scan controller)....
Compass Routing Suppose that (2008)
Suppose that a traveler arrives in the city ofToronto, and wants to walk to the famous CN Tower, one of the tallest free-standing structures in the world. Our visitor, lacking a map of Toronto, is...
Frank Akujobi, Ioannis Lambadaris, Evangelos Kranakis
Abstract—Fast spreading network worms have become one of the most service-impacting threats in enterprise and ISP networks. We identify core requirements for effective detection and containment of...
Constantinos Georgiou, Evangelos Kranakis, Ricardo Marcelín-jiménez, Rajsbaum Jorge Urrutia, Sergio Rajsbaum, Jorge Urrutia
This paper assumes a set of identical wireless hosts, each one aware of its location. The network is described by a unit distance graph whose vertices are points on the plane two of which are...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P, a flipturn involves reflecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grünbaum (1995)) showed that any polygon on n vertices...
– Eavesdropping – Identity malleability (2008)
Speaker Michel Barbeau, Contributors Jeyanthi Hall, Ph. C, Evangelos Kranakis
In this talk: • What are intrusion, intrusion prevention and intrusion detection? • Anomaly detection system architecture • Radio Frequency Fingerprinting (RFF) • Work in progress
Strategies for Hotlink Assignments (Extended Abstract) Prosenjit Bose (2008)
Jurek Czyzowicz, Leszek G Asieniec, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc
\Lambda z
Deterministic M2M Multicast in Radio Networks (Extended Abstract) (2008)
Leszek Gasieniec, Leszek G ˛asieniec, Evangelos Kranakis, Andrzej Pelc, Qin Xin
Leszek G asieniec 1? , Evangelos Kranakis 2?? , Andrzej Pelc 3? ? ? , and Qin Xin Department of Computer Science, University of Liverpool, Liverpool L69 7ZF, UK, {leszek,qinxin}@csc.liv.ac.uk School...
Securing the Destination-Sequenced Distance Vector (2008)
Routing Protocol Dsdv, Tao Wan, Evangelos Kranakis, P. C. Oorschot
A mobile ad hoc network (MANET) is formed by a group of mobile wireless nodes, each of which functions as a router and agrees to forward packets for others. Many routing protocols (e.g., AODV, DSDV,...
Games on Triangulations (2008)
Oswin Aichholzer David, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games---constructing, transforming, and marking...
Impact of Locality on Location Aware Unit Disk Graphs (2008)
Andreas Wiese, Evangelos Kranakis
Due to their importance for studies oi wireless networks, recent years have seen a surge of activity on the design of local algorithms for the solution of a variety of network tasks. We study the...
Jurek Czyzowicz, Leszek Gasieniec, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Miguel Vargas Martin
Consider a DAG (directed acyclic graph) G = (V; E) representing a collection V of web pages connected via links E. All web pages can be reached from a designated source page, represented by a source...
Baked Potatoes: Deadlock Prevention Via Scheduling (2007)
Shlomi Dolev, Evangelos Kranakis, Danny Krizanc
This paper identifies the equivalence of deadlock prevention in store-and-forward communication network and simultaneous arrival of packets to a switch of bufferless high-speed network. Scheduling of...
Domino Tilings of Orthogonal Polygons (2007)
Gyorgy Csizmadia, Jurek Czyzowicz, Leszek Gasieniec, Evangelos Kranakis, Jorge Urrutia
We consider orthogonal polygons with vertices located at integer lattice points. We show that if all of the sides of a simple orthogonal polygon without holes have odd lengths, then it cannot be...
Rigorous Results for Random (2+p)-SAT (2007)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc
In recent years there has been significant interest in the study of random k-SAT fomulae. For a given set of n Boolean variables, let B k denote the set of all possible disjunctions of k distinct,...
Domino Tilings of Orthogonal Polygons (2007)
György Csizmadia, Jurek Czyzowicz, Leszek Gasieniec, Evangelos Kranakis, Jorge Urrutia
We consider orthogonal polygons with vertices located at integer lattice points. We show that if all of the sides of a simple orthogonal polygon without holes have odd lengths, then it cannot be...
Leader Election and Sorting in Anonymous Asynchronous Rings 1 (2007)
Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Flaminia L. Luccio, Nicola Santoro
In an anonymous ring of n processors, all processors are totally indistinguishable except for their input values. These values are not necessarily distinct, i.e., they form a multiset, and this makes...
Krzysztof Diks, Pierre Fraigniaud, Evangelos Kranakis, Andrzej Pelc
A robot with k-bit memory has to explore a tree whose nodes are unlabeled and edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the tree or of its...
On the falsepositive rate of Bloom filters (2007)
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, ...
Abstract. Bloom filters are a randomized data structure for membership queries dating back to 1970. Bloom filters sometimes give erroneous answers to queries, called false positives. Bloom analyzed...
Playing with Triangulations (2007)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Abstract. We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games: constructing, transforming, and marking...
Evangelos Kranakis, Danny Krizanc, Miguel Vargas Martin
The Hotlink Optimizer (HotOpt) is a new software tool that helps administrators and designers to structure their web sites eciently. We propose an improvement on web site access by making the most...
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
9 1
Evangelos Kranakis, Danny Krizanc, Miguel Vargas Martin
The Hotlink Optimizer (HotOpt) is a new software tool that helps administrators and designers to structure their websites eciently. We propose an improvement on website access by making the most...
Evangelos Kranakis, Andrzej Pelc, Anthony Spatharis
We study adaptive system-level fault diagnosis for multiprocessor systems. Processors can test each other and future tests can be selected on the basis of previous test results. Fault-free testers...
Prosenjit Bose, Evangelos Kranakis, Christos Kaklamanis, Lefteris M. Kirousis, Danny Krizanc, David Peleg
In wireless communication, the signal of a typical broadcast station is transmitted from a broadcast center p and reaches objects at a distance, say, r from it. In addition there is a radius r0, r0...
Evangelos Kranakis, Danny Krizanc
Abstract. We investigate the notion of Long Range Contact graphs. Roughly speaking, such a graph is defined by (1) an underlying network topology G, and (2) one (or possibly more) extra link...
Krzysztof Diks, Evangelos Kranakis, Andrzej Pelc
We consider broadcasting a message from one node to all other nodes of an asynchronous totally unlabeled network: neither nodes nor links of the network have a priori assigned labels but they know...
Krzysztof Diks, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc
The impact of knowledge on broadcasting time in radio networks
Nicolas Hanusse, Dimitris Kavvadias, Evangelos Kranakis, Danny Krizanc
Abstract In this paper, we present a randomized algorithm for a mobile agent to search for an item t stored at a node of a network, without prior knowledge of its exact location. Each node of the...
Evangelos Kranakis, Danny Krizanc, Nicola Santoro, Cindy Sawchuk
In the rendezvous search problem, two mobile agents must move along the n nodes of a network so as to minimize the time required to meet or rendezvous. When the mobile agents are identical and the...
Lefteris M. Kirousis, Evangelos Kranakis, Yannis C. Stamatiou
Abstract. We consider the problem of searching for a piece of information in a fully interconnected computer network (also called complete network or clique) by exploiting advice about its location...
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
9 1
Evangelos Kranakis, Danny Krizanc, Sunil Shende
Abstract. Consider a directed rooted tree T = (V; E) of maximal degree d representing a collection V of web pages connected via a set E of links all reachable from a source home page, represented by...
Hee-kap Ahn, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
z Universite du Quebec a Hull.
Searching with Uncertainty (Extended Abstract) (2007)
Evangelos Kranakis, Danny Krizanc
We consider the problem of searching for an item in a distributed network in the presence of uncertainty. Although the location of the item in the network is unknown, information about its...
Alexis C. Kaporis, Lefteris M. Kirousis, Evangelos Kranakis, Yannis C. Stamatiou, C. Stavropoulos
In this paper we examine the problem of searching for some information item in the nodes of a fully interconnected computer network, where each node contains information relevant to some topic as...
Hee-kap Ahn, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Figure 1: An example of a ipturn. Given a polygon P, a ipturn involves re ecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed...
Evangelos Kranakis, Danny Krizanc, Nicola Santoro, Cindy Sawchuk
In the rendezvous search problem, two mobile agents must move along the n nodes of a network so as to minimize the time required to meet or rendezvous. When the mobile agents are identical and the...
Krzysztof Diks, Evangelos Kranakis, Andrzej Pelc, Instytut Informatyki, Uniwersytet Warszawski
We consider broadcasting a message from one node to all other nodes of an asynchronous totally unlabeled network: neither nodes nor links of the network have a priori assigned labels but they know...
Deterministic M2M Multicast in Radio Networks (Extended Abstract) (2007)
Leszek Gasieniec, Leszek G ˛asieniec, Evangelos Kranakis, Andrzej Pelc, Qin Xin
Leszek G asieniec # , Evangelos Kranakis ### , Andrzej Pelc ##### , and Qin Xin # # Department of Computer Science, University of Liverpool, Liverpool L69 7ZF, UK, {leszek,qinxin}@csc.liv.ac.uk #...
RANDOMIZED RENDEZ-VOUS WITH LIMITED MEMORY (2007)
Evangelos Kranakis, Danny Krizanc, Pat Morin
Abstract. We present a tradeoff between the expected time for two identical agents to rendez-vous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular,...
Mobile agent rendezvous in a synchronous torus (2006)
Evangelos Kranakis, Danny Krizanc, Euripides Markou
Abstract. We consider the rendezvous problem for identical mobile agents (i.e., running the same deterministic algorithm) with tokens in a synchronous torus with a sense of direction and show that...
Incremental Construction of k-Dominating Sets in Wireless Sensor Networks (2006)
Mathieu Couture, Michel Barbeau, Prosenjit Bose, Evangelos Kranakis
Given a graph G, a k-dominating set of G is a subset S of its vertices with the property that every vertex of G is either in S or has at least k neighbors in S. We present a new incremental local...
Location Oblivious Distributed Unit Disk Graph Coloring (2006)
We present the first location oblivious distributed unit disk graph coloring algorithm having a provable performance ratio of three (i.e. the number of colors used by the algorithm is at most three...
David Whyte, P. C. Oorschot, Evangelos Kranakis
Current scanning detection algorithms are based on an underlying assumption that scanning activity can be attributed to a meaningful specific source (i.e. the root cause or scan controller)....
Detecting Intra-Enterprise Scanning Worms Based on Address Resolution (2005)
David Whyte, Evangelos Kranakis
Signature-based schemes for detecting Internet worms often fail on zero-day worms, and their ability to rapidly react to new threats is typically limited by the requirement of some form of human...
Approximate Range Mode and Range Median Queries (2005)
Prosenjit Bose, Evangelos Kranakis, Pat Morin, Yihui Tang
ABSTRACT. Mode and median are two of the most important statistics we use when we analyze data. In this paper, we consider data structures and algorithms for preprocessing a labelled list of length n...
Oorschot. Pretty secure BGP (psBGP (2005)
Tao Wan, Evangelos Kranakis, P. C. Oorschot
The Border Gateway Protocol (BGP) is an IETF standard inter-domain routing protocol on the Internet. However, it is well known that BGP is vulnerable to a variety of attacks, and that a single...
Half-space proximal: A new local test for extracting a bounded dilation spanner (2005)
Edgar Chavez, Stefan Dobrev, Evangelos Kranakis, Jaroslav Opatrny, Ladislav Stacho, Héctor Tejeda, ...
Abstract. We give a new local test, called a Half-Space Proximal or HSP test, for extracting a sparse directed or undirected subgraph of a given unit disk graph. The HSP neighbors of each vertex are...
Oorschot. Pretty secure BGP (psBGP (2005)
Tao Wan, Evangelos Kranakis, P. C. Oorschot
The Border Gateway Protocol (BGP) is the de-facto standard inter-domain routing protocol on the Internet. However, it is well known that BGP is vulnerable to a variety of types of attacks, and that a...
DNS-based Detection of Scanning Worms in an Enterprise Network (2005)
David Whyte Evangelos, Evangelos Kranakis, P. C. Oorschot
Worms are arguably the most serious security threat facing the Internet. Seeking a detection technique that is both sufficiently efficient and accurate to enable automatic containment of worm...
Detecting Intra-enterprise Scanning Worms based on Address Resolution (2005)
David Whyte Paul, Evangelos Kranakis
Signature-based schemes for detecting Internet worms often fail on zero-day worms, and their ability to rapidly react to new threats is typically limited by the requirement of some form of human...
Approximate Range Mode And Range Median Queries (2005)
Prosenjit Bose Evangelos, Evangelos Kranakis, Pat Morin, Yihui Tang
We consider data structures and algorithms for preprocessing a labelled list of length n so that, for any given i and j we can answer queries of the form: What is the mode or median label in the...
Detecting Impersonation Attacks in Future Wireless and Mobile Networks (2005)
Michel Barbeau, Jyanthi Hall, Evangelos Kranakis
Abstract. Impersonation attacks in wireless and mobile networks by professional criminal groups are becoming more sophisticated. We confirm with simple risk analysis that impersonation attacks offer...
Oorschot. Pretty secure BGP (psBGP (2005)
Tao Wan, Evangelos Kranakis, P. C. Oorschot
The Border Gateway Protocol (BGP) is the de-facto standard inter-domain routing protocol on the Internet. However, it is well known that BGP is vulnerable to a variety of types of attacks, and that a...
Anomaly-based intrusion detection using mobility profiles of public transportation users (2005)
Jeyanthi Hall, Michel Barbeau, Evangelos Kranakis
Abstract — For the purpose of anomaly-based intrusion detection in mobile networks, the utilization of profiles based on hardware signatures, calling patterns, service usage and mobility patterns...
Approximate Range Mode and Range Median Queries (2005)
Prosenjit Bose, Evangelos Kranakis, Pat Morin, Yihui Tang
Abstract. We consider data structures and algorithms for preprocessing a labelled list of length n so that, for any given indices i and j we can answer queries of the form: What is the mode or median...
Detecting Impersonation Attacks in Future Wireless and Mobile Networks (2005)
Michel Barbeau, Jyanthi Hall, Evangelos Kranakis
Abstract. Impersonation attacks in wireless and mobile networks by professional criminal groups are becoming more sophisticated. We confirm with simple risk analysis that impersonation attacks offer...
Anomaly-based intrusion detection using mobility profiles of public transportation users (2005)
Jeyanthi Hall, Michel Barbeau, Evangelos Kranakis
Abstract — For the purpose of anomaly-based intrusion detection in mobile networks, the utilization of profiles, based on hardware signatures, calling patterns, service usage, and mobility...
Oorschot. DNS-based detection of scanning worms in an enterprise network (2005)
David Whyte, Evangelos Kranakis, P. C. Oorschot
Worms are arguably the most serious security threat facing the Internet. Seeking a detection technique that is both sufficiently efficient and accurate to enable automatic containment of worm...
On Inter-domain Routing Security and Pretty Secure BGP (psBGP (2005)
It is well known that the Border Gateway Protocol (BGP), the IETF standard inter-domain routing protocol, is vulnerable to a variety of attacks, and that a single misconfigured or malicious BGP...
Jeyanthi Hall, Michel Barbeau, Evangelos Kranakis
Media access control (MAC) address spoofing results in the theft of sensitive information and misuse of network resources. This paper demonstrates an anomaly-based intrusion detection approach, which...
Security Issues in the Border Gateway Protocol (BGP) (2005)
Evangelos Kranakis, P. C. Oorschot, Tao Wan
The Internet has become a critical communication infrastructure which we are increasingly reliant upon. As the world moves into a converged network where voice, video, and data are all transmitted...
Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency (2005)
CLOTE, PETER, FERRÉ, FABRIZIO, KRANAKIS, EVANGELOS, KRIZANC, DANNY
We present results of computer experiments that indicate that several RNAs for which the native state (minimum free energy secondary structure) is functionally important (type III hammerhead...
Improved Approximation Algorithms for Connected Sensor Cover (2004)
Funke, Stefan, Kesselmann, Alexander, Lotker, Zvi, Segal, Michael, Nikolaidis, Ioanis, Barbeau, Michel, ...
Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and...
Improving Distance Based Geographic Location Techniques (2004)
Michel Barbeau, Evangelos Kranakis, Danny Krizanc, Pat Morin
Abstract. Supporting nodes without Global Positioning System (GPS) capability, in wireless ad hoc and sensor networks, has numerous applications in guidance and surveying systems in use today. At...
S-RIP: A Secure Distance Vector Routing Protocol (2004)
Tao Wan, Evangelos Kranakis, P. C. Oorschot
Abstract. Distance vector routing protocols (e.g., RIP) have been widely used on the Internet, and are being adapted to emerging wireless ad hoc networks. However, it is well-known that existing...
Evangelos Kranakis, Danny Krizanc, Eric Williams
A network is k-connected if it remains connected after the removal of any k − 1 of its nodes. Assume that n sensors, modeled here as (omni)directional antennas, are dropped randomly and...
S-RIP: A Secure Distance Vector Routing Protocol (2004)
Tao Wan, Evangelos Kranakis, P. C. Oorschot
Abstract. Distance vector routing protocols (e.g., RIP) have been widely used on the Internet, and are being adapted to emerging wireless ad hoc networks. However, it is well-known that existing...
S-RIP: A Secure Distance Vector Routing Protocol (2004)
Distance vector routing protocols (e.g., RIP) have been widely used on the Internet, and are being adapted to emerging wireless ad hoc networks.
S-RIP: A Secure Distance Vector Routing Protocol (2004)
Tao Wan Evangelos, Tao Wan, Evangelos Kranakis, P. C. Oorschot
Distance vector routing protocols (e.g., RIP) have been widely used on the Internet, and are being adapted to emerging wireless ad hoc networks.
Improved Approximation Algorithms for Connected Sensor Cover (2004)
Funke, Stefan, Kesselmann, Alexander, Lotker, Zvi, Segal, Michael, Nikolaidis, Ioanis, Barbeau, Michel, ...
Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and...
Mobile agent rendezvous in a ring (2003)
Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Nicola Santoro, Cindy Sawchuk
We study the rendezvous search problem for k 2 mobile agents in an n node ring. Rather than using randomized algorithms or dierent deterministic algorithms to break the symmetry that often arises in...
Improving web server’s data transfer with hotlinks (2003)
Evangelos Kranakis, Danny Krizanc, Miguel Vargas Martin
We study the optimization of the expected number of bytes that must be transferred by a Web server when a user visits one of its pages. Given a Web site, we want to find an assignment of hotlinks...
Multiple Mobile Agent Rendezvous in a Ring Paola Flocchini \Lambda (2003)
Evangelos Kranakis, Danny Krizanc, Nicola Santoro, Cindy Sawchuk
y
XSTP: eXtended Satellite Transport Protocol (2003)
Maged E. Elaasar, Zheyin Li, Michel Barbeau, Evangelos Kranakis
Being both wireless and mobile, LEO satellite access networks have a unique set of link errors including bit corruption, handoff and limited connectivity. Unfortunately, most transport protocols are...
Resisting Malicious Packet Dropping in Wireless Ad Hoc Networks (2003)
Mike Just, Evangelos Kranakis, Tao Wan
Abstract. Most of the routing protocols in wireless ad hoc networks, such as DSR, assume nodes are trustworthy and cooperative. This assumption renders wireless ad hoc networks vulnerable to various...
Michel Barbeau, E. Kranakis, Evangelos Kranakis
Michel Barbeau Evangelos Kranakis School of Computer Science Carleton University Ottawa, Canada Email: fbarbeau,kranakisg@scs.carleton.ca Abstract---We define post-query strategies: these are time...
Optimizing Web Server's Data Transfer With (2003)
Hotlinks Evangelos Kranakis, Evangelos Kranakis, Danny Krizanc, Miguel Vargas Martin
We study the optimization of the expected number of bytes that must be transferred by the Web server when a user visits one of its pages. Given a Web site, we want to find an assignment of hotlinks...
Resisting Malicious Packet Dropping in Wireless Ad Hoc Networks (2003)
Mike Just, Evangelos Kranakis, Tao Wan
Abstract. Most of the routing protocols in wireless ad hoc networks, such as DSR, assume nodes are trustworthy and cooperative. This assumption renders wireless ad hoc networks vulnerable to various...
Kranakis,Evangelos, Vitanyi,Paul M.
The number of messages to match a pair of processes in a multiprocessor network with mobile processes is a measure for the cost of setting up temporary communication between processes. The authors...
Improving customer proximity to railway stations (2002)
Evangelos Kranakis, Paolo Penna, Konrad Schlude, David Scot Taylor, Peter Widmayer
We consider problems of (nev) station placement along (existing) railvay tracks, so as to increase the number of users. We prove that, in spite of the NP-hardness for the general version, some...
Improving customer proximity to railway stations (2002)
Evangelos Kranakis, Paolo Penna, Konrad Schlude, David Scot Taylor, Peter Widmayer
Abstract. We consider problems of (new) station placement along (existing) railway tracks, so as to increase the number of users. We prove that, in spite of the NP-hardness for the general version,...
Optimal Assignment of Bookmarks to Web Pages (2002)
Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Miguel Vargas Martin
yzk
Improving customer proximity to railway stations (2002)
Evangelos Kranakis, Paolo Penna, Konrad Schlude, David Scot Taylor, Peter Widmayer
Abstract. We consider problems of (new) station placement along (existing) railway tracks, so as to increase the number of users. We prove that, in spite of the NP-hardness for the general version,...
Improving customer proximity to railway stations (2002)
Evangelos Kranakis, Paolo Penna, Konrad Schlude, David Scot Taylor, Peter Widmayer
We consider problems of (nev) station placement along (existing) railvay tracks, so as to increase the number of users. We prove that, in spite of the NP-hardness for the general version, some...
Tree Exploration with Little Memory (2002)
Krzysztof Diks Pierre, Pierre Fraigniaud, Evangelos Kranakis, Andrzej Pelc
A robot with k-bit memory has to explore a tree whose nodes are unlabeled and edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the tree or of its...
Tree Exploration with Little Memory (2002)
Krzysztof Diks Pierre, Pierre Fraigniaud, Evangelos Kranakis, Andrzej Pelc
A robot with k-bit memory has to explore a tree whose nodes are unlabeled and edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the tree or of its...
Alexis C. Kaporis, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou, Elias C. Stavropoulos
zyy
Evaluation of Hotlink Assignment Heuristics for Improving Web Access (2001)
Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Miguel Vargas Martin
We study the optimal hotlink assignment problem. Consider a web site as a directed graph, where each page is represented by a node and each link is represented by an edge. The resulting graph is...
Efficient Routing in Networks with Long Range Contacts (2001)
Lali Barrière, Pierre Fraigniaud, Evangelos Kranakis, Danny Krizanc
We investigate the notion of Long Range Contact graphs. Roughly speaking, such a graph is defined by (1) an underlying network topology G, and (2) one (or possibly more) extra link connecting every...
WPP: A Secure Payment Protocol (2001)
Jeyanthi Hall, Susan Kilbank, Michel Barbeau, Evangelos Kranakis
The proliferation of wireless devices, offering connectivity and convenience, continues to exert tremendous pressure on merchants to deploy secure wireless applications including electronic commerce.
Kaporis, Alexis C., Kirousis, Lefteris M., Kranakis, Evangelos, Krizanc, Danny, Stamatiou, Yannis C., Stavropoulos, Elias C.
In this paper we examine the problem of searching for some information item in the nodes of a fully interconnected computer network, where each node contains information relevant to some topic as...
Searching with mobile agents in networks with liars (2000)
Nicolas Hanusse, Evangelos Kranakis, Danny Krizanc
We present deterministic algorithms to search for an item s contained in a node of a network, without prior knowledge of its exact location. Each node of the network has a database that will answer...
Power consumption in packet radio networks (2000)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc
zy
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Hee-kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. We show that any polygon on n vertices will be convex after any sequence of at most n(n 3)=2...
Hee-Kap Ahn, Prosenjit Bose, Jurek Czyzowicz, Nicolas Hanusse, Evangelos Kranakis, Pat Morin
Given a polygon P , a ipturn involves reecting a pocket p of P through the midpoint of the lid of p. In 1973, Joss and Shannon (published in Grunbaum (1995)) showed that any polygon on n vertices...
Bubbles: Adaptive routing scheme for high-speed dynamic networks (1999)
Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg
This paper presents the first dynamic routing scheme for high-speed networks. The scheme is based on a hierarchical bubbles partition of the underlying communication graph. Dynamic routing schemes...
Near-Optimal Partitioning of Rectangles and Prisms (1999)
Prosenjit Bose, Jurekk Czyzowicz, Evangelos Kranakis, Danny Krizanc, Dominic Lessard
This paper focuses on the following problems:
Near-Optimal Partitioning of Rectangles and Prisms (1999)
Prosenjit Bose, Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Dominic Lessard
This paper focuses on the following problems:
Compass Routing on Geometric Networks (1999)
Evangelos Kranakis, Harvinder Singh, Jorge Urrutia
this paper we study local routing algorithms on geometric networks. Formally speaking, suppose that we want to travel from a vertex s to a vertex t of a geometric network. A routing algorithm is...
Near-Optimal Partitioning of Rectangles and Prisms (1999)
Prosenjit Bose, Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Dominic Lessard
This paper focuses on the following problems:
Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks (1999)
Extend Ed, Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg
) Shlomi Dolev Evangelos Kranakis y Danny Krizanc y David Peleg z Abstract This paper presents the first dynamic routing scheme for high-speed networks. The scheme is based on a hierarchical bubbles...
Discrete Realizations of Contact and Intersection Graphs (Extended Abstract) (1998)
Czyzowicz, Jurek, Kranakis, Evangelos, Krizanc, Danny, Urrutia, Jorge
Known realizations of geometric representations of graphs, like contact, intersection etc., are "continuous", in the sense that the geometric objects are drawn in Euclidean space with real numbers as...
Discrete Realizations of Contact and Intersection Graphs (Extended Abstract) (1998)
Czyzowicz, Jurek, Kranakis, Evangelos, Krizanc, Danny, Urrutia, Jorge
Known realizations of geometric representations of graphs, like contact, intersection etc., are "continuous", in the sense that the geometric objects are drawn in Euclidean space with real numbers as...
Discrete Realizations of Contact and Intersection Graphs (Extended Abstract) (1998)
Czyzowicz, Jurek, Kranakis, Evangelos, Krizanc, Danny, Urrutia, Jorge
Known realizations of geometric representations of graphs, like contact, intersection etc., are "continuous", in the sense that the geometric objects are drawn in Euclidean space with real numbers as...
Approximating the unsatisfiability threshold of random formulas (1998)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
ABSTRACT: Let � be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number � such that if the ratio of the number of clauses over the...
Broadcasting in unlabeled hypercubes with linear number of messages (1998)
Krzysztof Diks, Stefan Dobrev, Evangelos Kranakis, Andrzej Pelc, Peter Ruzicka
We consider broadcasting a message from one node to all other nodes of an asynchronous totally unlabeled n-node hypercube. Neither nodes nor links have a priori assigned labels. We show a...
Algorithms for packing two circles in a convex polygon (1998)
Jurek Czyzowicz, Evangelos Kranakis, Anil Maheshwari
Abstract. We consider algorithms for packing two circles in a given n-vertex convex polygon. The rst algorithm outputs a pair of equal non-overlapping circles of maximum radius and has running time...
Approximating the unsatisfiability threshold of random formulas (1998)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
zx
Two Topics in Applied Algorithmics (1998)
Patrick R. Morin, Patrick R. Morin, Patrick R. Morin, Dr. Evangelos Kranakis
This thesis examines two largely unrelated problems in applied algorithmics, motivated by the search for efficient geometric algorithms. In the first part of the thesis, we consider the problem of...
Efficient Regular Polygon Dissections (1998)
Evangelos Kranakis, Danny Krizanc, Jorge Urrutia
We study the minimum number g(m, n) (respectively, p(m, n)) of pieces needed to dissect a regular m-gon into a regular n-gon of the same area using glass-cuts (respectively, polygonal cuts). First we...
Fault-Tolerant Broadcasting in Radio Networks (1998)
Evangelos Kranakis, Danny Krizanc, Andrzej Pelc
We consider broadcasting in radio networks that are subject to permanent node failures of unknown location. Nodes are spread in a region in some regular way. We consider two cases: nodes are either...
Broadcasting in Unlabeled Tori (1998)
Krzysztof Diks, Evangelos Kranakis, Andrzej Pelc
We consider broadcasting a message from one node to all other nodes of an asynchronous totally unlabeled torus: neither nodes nor links have a priori assigned labels but they know the topology and...
Random Constraint Satisfaction: A More Accurate Picture (1998)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
In the last few years there has been a great amount of interest in Random Constraint Satisfaction Problems, both from an experimental and a theoretical point of view. Quite intriguingly, experimental...
Rigorous Results for Random (2+p)-SAT (1997)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc
zk
Random constraint satisfaction: A more accurate picture (1997)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
zk
Random constraint satisfaction: A more accurate picture (1997)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
y--
Random Constraint Satisfaction: A More Accurate Picture (1997)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
. In the last few years there has been a great amount of interest in Random Constraint Satisfaction Problems, both from an experimental and a theoretical point of view. Quite intriguingly,...
Random Constraint Satisfaction: A More Accurate Picture (1997)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
. In the last few years there has been a great amount of interest in Random Constraint Satisfaction Problems, both from an experimental and a theoretical point of view. Quite intriguingly,...
Boolean Routing on Cayley Networks (1997)
Evangelos Kranakis, Danny Krizanc
We study Boolean routing on Cayley networks. Let K(MG ) denote the Kolmogorov complexity of the multiplication table of a group G of order n. We show that O(maxfd log n; K(MG )g) memory bits per...
Rigorous Results for Random (2+p)-SAT (1997)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc
Consider random k-SAT instances with rn clauses over n variables, where each clause is chosen uniformly and independently from the set of all clauses of length k. It is widely believed that for all k...
Random Constraint Satisfaction: A More Accurate Picture (1997)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
Recently there has been a great amount of interest in Random Constraint Satisfaction Problems, both from an experimental and a theoretical point of view. Rather intriguingly, experimental results...
Random Constraint Satisfaction: A More Accurate Picture (1997)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Michael S.O., ...
Recently there has been a great amount of interest in Random Constraint Satisfaction Problems, both from an experimental and a theoretical point of view. Rather intriguingly, experimental results...
Random constraint satisfaction: A more accurate picture (1997)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatioux
A Better Upper Bound for the Unsatisfiability Threshold (1996)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc
. Let OE be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number such that if the ratio of the number of clauses over the number of...
For k = 1; 2; 3 we characterize the domino tilings of n \Theta n squares which have exactly k nonoverlapping 2 \Theta 2 squares. 1980 Mathematics Subject Classification: 68R05 CR Categories: G.2.1...
Maximal Length Common Non-Intersecting Paths (1996)
Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Jorge Urrutia
Given a set P n of n points on the plane labeled with the integers f1; : : : ; ng, an increasing path of P n is a sequence of points i 1 ! : : : ! i k such that the polygonal path obtained by...
A Correlation Inequality and Its Application to a Word Problem (1996)
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Michael S. Molloy
We give upper bounds for the probability that a random word of a given length contains at least one letter from each member of a given collection of sets of letters. We first show a correlation...
An Upper Bound for a Basic Hypergeometric Series (1996)
Lefteris Kirousis, Evangelos Kranakis, Danny Krizanc
We show that if 0 x 2 q 1, then the basic hypergeometric series P n k=0 \Gamma n k \Delta q x k is bounded above by the product Q n\Gamma1 k=0 (1 + xq k=2 ). AMS Mathematics Subject Classification...
Approximating the Unsatisfiability Threshold of Random Formulas (1996)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
Let OE be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number such that if the ratio of the number of clauses over the number of...
Power Consumption in Packet Radio Networks (Extended Abstract) (1996)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc
) Lefteris M. Kirousis x (kirousis@cti.gr) Evangelos Kranakis y (kranakis@scs.carleton.ca) Danny Krizanc y (krizanc@scs.carleton.ca) Andrzej Pelc zy (pelc@uqah.uquebec.ca) Abstract In this paper we...
Symmetry and Computability in Anonymous Networks: A Brief Survey (1996)
. Processors in anonymous networks are as identical to each other as possible and possess "little" knowledge about the network. Anonymous networks are very useful in theoretical studies for...
On the Number of Directions in Visibility Representations of Graphs (Extended Abstract) (1995)
Kranakis, Evangelos, Krizanc, Danny, Urrutia, Jorge
We consider visibility representations of graphs in which the vertices are presented by a collection O of non-overlapping convex regions on the plane. Two points x and y are visible if the...
On the Number of Directions in Visibility Representations of Graphs (Extended Abstract) (1995)
Kranakis, Evangelos, Krizanc, Danny, Urrutia, Jorge
We consider visibility representations of graphs in which the vertices are presented by a collection O of non-overlapping convex regions on the plane. Two points x and y are visible if the...
On the Number of Directions in Visibility Representations of Graphs (Extended Abstract) (1995)
Kranakis, Evangelos, Krizanc, Danny, Urrutia, Jorge
We consider visibility representations of graphs in which the vertices are presented by a collection O of non-overlapping convex regions on the plane. Two points x and y are visible if the...
Anonymous wireless rings (1995)
Krzysztof Diks, Evangelos Kranakis, Adam Malinowski, Andrzej Pelc
yx
String Recognition on Anonymous Rings (1995)
Evangelos Kranakis, Danny Krizanc, Flaminia L. Luccio
Abstract. We consider the problem of recognizing whether a given binary string of length n is equal (up to rotation) to the input of an anonymous oriented ring of n processors. Previous algorithms...
Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks (1995)
Shlomi Dolev, Evangelos Kranakis, Danny Krizanc
We present the first dynamic routing schemes for high-speed networks. The scheme is based on a hierarchical bubbles partition of the underlying communication graph. We rank dynamic routing schemes by...
Approximating the Unsatisfiability Threshold of Random Formulas (1995)
Lefteris Kirousis Kirousis, Evangelos Kranakis, Danny Krizanc
Let OE be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number such that if the ratio of the number of clauses over the number of...
Stage-Graph Representations (1995)
Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Marc Noy, Jörg-Rüdiger Sack, Jorge Urrutia
We consider graph applications of the well-known paradigm "killing two birds with one stone". In the plane, this gives rise to a stage graph as follows: vertices are the points, and fu; vg...
On the Number of Directions in Visibility Representations of Graphs (Extended Abstract) (1995)
Evangelos Kranakis, Danny Krizanc, Jorge Urrutia
) Evangelos Kranakis 1 (kranakis@scs.carleton.ca) Danny Krizanc 1 (krizanc@scs.carleton.ca) Jorge Urrutia 2 (jorge@csi.uottawa.ca) 1 Carleton University, School of Computer Science, Ottawa, ON,...
Approximating the Unsatisfiability Threshold of Random Formulas (1995)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
Let OE be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number such that if the ratio of the number of clauses over the number of...
Complexity of Boolean Routing (Extended Abstract) (1995)
Evangelos Kranakis, Danny Krizanc, Jorge Urrutia
) Evangelos Kranakis y (kranakis@scs.carleton.ca) Danny Krizanc y (krizanc@scs.carleton.ca) Jorge Urrutia zy (jorge@csi.uottawa.ca) Abstract We use the technique of Kolmogorov complexity to obtain...
Ray Shooting from Convex Ranges (1995)
Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Jörg-Rüdiger Sack, Jorge Urrutia
We consider geometric and graph-theoretic aspects of the well-known paradigm "killing two birds with one stone". Consider that we have a set X of n-points in space and a compact plane...
Planar Stage Graphs: Characterizations And Applications (1995)
Frank Bauernöppel, Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Jörg-Rüdiger Sack, Jorge Urrutia
We consider combinatorial and algorithmic aspects of the well-known paradigm "killing two birds with one stone". We define a stage graph as follows: vertices are the points from a planar...
Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, David Peleg
A function is distributed among nodes of a graph in a continuous way, i.e., such that the difference between values stored at adjacent nodes is small. The goal is to find a node of maximum value by...
Implicit Routing And Shortest Path Information (Extended Abstract) (1995)
E. Kranakis, D. Krizanc, Evangelos Kranakis, Danny Krizanc, J. Urrutia
) Evangelos Kranakis y (kranakis@scs.carleton.ca) Danny Krizanc y (krizanc@scs.carleton.ca) Jorge Urrutia zy (jorge@csi.uottawa.ca) Abstract We study the problem of constructing graphs from shortest...
Hop-Congestion Tradeoffs For Atm Networks (1995)
Evangelos Kranakis, Danny Krizanc, Andrzej Pelc
In ATM networks messages are transmitted through virtual paths. Packets are routed along virtual paths by maintaining a routing field whose subfields determine the intermediary destinations of the...
An Improved Maximum Matching Algorithm in a Permutation Graph (1995)
Frank Bauernöppel, Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Jörg-Rüdiger Sack, Jorge Urrutia
Introduction We present an O(n log 2 n) time algorithm for computing a maximum matching in a permutation graph on n-vertices. Our results are based on the algorithm of [12] for a two processor...
Lower Bounds for Compact Routing (Extended Abstract) (1995)
Evangelos Kranakis, Danny Krizanc
In this paper we present lower bounds for compact routing schemes. We give (1) networks on n vertices which for any interval routing scheme,\Omega\Gamma n) routers of the network require\Omega\Gamma...
Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks (Extended Abstract) (1995)
Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg
) Shlomi Dolev Evangelos Kranakis y Danny Krizanc y David Peleg z Abstract This paper presents the first dynamic routing scheme for high-speed networks. The scheme is based on a hierarchical bubbles...
String Recognition on Anonymous Rings (1995)
Evangelos Kranakis, Danny Krizanc, Flaminia L. Luccio
. We consider the problem of recognizing whether a given binary string of length n is equal (up to rotation) to the input of an anonymous oriented ring of n processors. Previous algorithms for this...
Approximating the Unsatisfiability Threshold of Random Formulas (Extended Abstract) (1995)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc
Let OE be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number such that if the ratio of the number of clauses over the number of...
Isomorphic Triangulations with Minimal Number of Steiner Points (Extended Abstract) (1994)
Evangelos Kranakis, Jorge Urrutia, Steiner Points
We present two algorithms for constructing isomorphic (i.e. adjacency preserving) triangulations of two simple n vertex polygons P, Q with k, l reflex vertices, respectively. The first algorithm...
On Key Distribution via True Broadcasting (1994)
Mike Just, Evangelos Kranakis, Danny Krizanc, Paul Van Oorschot
We consider true broadcast systems for the secure communication of session keys. These schemes provide for parallel rather than serial construction of broadcast messages, while avoiding selective...
String Recognition On Anonymous Rings (1994)
Evangelos Kranakis, Danny Krizanc, Flaminia L. Luccio
We consider the problem of recognizing whether a given binary string of length n is equal (up to rotation) to the input of an anonymous oriented ring of n processors. Previous algorithms for this...
VC-Dimensions For Graphs (1994)
Evangelos Kranakis, Danny Krizanc, Berthold Ruf, Jorge Urrutia, Gerhard J. Woeginger
We study set systems over the vertex set (or edge set) of some graph that are induced by special graph properties like clique, connectedness, path, star, tree, etc. We derive a variety of...
Broadcasting Session Keys (1994)
Mike Just, Evangelos Kranakis, Danny Krizanc, Paul Van Oorschot
This paper considers true broadcast systems for the secure communication of session keys. These are schemes that provide for parallel rather than serial construction of broadcast messages, while...
Distributed computing on anonymous hypercubes with Faulty Components (1992)
Evangelos Kranakis, Nicola Santoro
We give ecient algorithms for distributed computation on anonymous, labeled, asynchronous hypercubes with possible faulty components (i.e. processors and links) and deterministic procoessors....
A Note on Weighted Distributed Match-Making (1992)
This is a preliminary draft version of [Mathematical Systems Theory, 25(1992), 123-140]. In many distributed computing environments, processes are concurrently executed by nodes in a...
Camera Placement in Integer Lattices (1992)
Evangelos Kranakis, Evangelos Kranakis, Michel Pocchiola, Michel Pocchiola
The camera placement problem concerns the placement of a fixed number of point-cameras on the integer lattice of d-tuples of integers in order to maximize their visibility. We give a caracterization...
A Brief Survey of Art Gallery Problems in Integer Lattice Systems (1991)
Evangelos Kranakis, Evangelos Kranakis, Michel Pocchiola, Michel Pocchiola
The camera placement problem concerns the placement of a fixed number of point-cameras on the integer lattice of d-tuples of integers in order to maximize their visibility. We survey some of the...
Recursive analogues of large cardinals /--by Evangelos Kranakis. (1980)
Thesis (Ph. D.)--University of Minnesota, 1980.
Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency
CLOTE, PETER, FERRÉ, FABRIZIO, KRANAKIS, EVANGELOS, KRIZANC, DANNY
We present results of computer experiments that indicate that several RNAs for which the native state (minimum free energy secondary structure) is functionally important (type III hammerhead...
Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency
CLOTE, PETER, FERRÉ, FABRIZIO, KRANAKIS, EVANGELOS, KRIZANC, DANNY
We present results of computer experiments that indicate that several RNAs for which the native state (minimum free energy secondary structure) is functionally important (type III hammerhead...
Polygon Cutting: Revisited Prosenjit Bose
Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Anil Maheshwari
Abstract. Given a simple polygon P on n vertices v0; v1; : : : ; vn 1 with each edge assigned a non-negative weight w i, we show how to compute in O(n) time a segment v i b (where b is a point on the...