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...
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES (2009)
Prosenjit Bose, Vida Dujmović, Danny Krizanc, Stefan Langerman, Pat Morin
Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Anup Patnaik, Sunil Shende
with uncertainty in the position of the destination
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 Abstract Mobile Agent Rendezvous in a Ring (2008)
In the rendezvous search problem, two mobile agents must move along the ¢ nodes of a network so as to minimize the time required to meet or rendezvous. When the mobile agents are identical and the...
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES (2008)
Prosenjit Bose, Danny Krizanc, Stefan Langerman, Pat Morin
Abstract A graph G is a 2-tree if G = K3, or G has a vertex vof degree 2, whose neighbours are adjacent, and G \ vis a 2-tree. A characterization of the degree sequences of 2-trees is given. This...
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.
Chapter 1 RANDOM SAMPLING: SORTING AND SELECTION (2008)
Danny Krizanc, Sanguthevar Rajasekaran
Abstract Random sampling techniques have played a vital role in the design of sorting and selection algorithms for numerous models of computing. In this article we provide a summary of sorting and...
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES (2008)
Prosenjit Bose, Vida Dujmović, Danny Krizanc, Stefan Langerman, Pat Morin
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
Dynamic Interval Routing on Asynchronous Rings (2008)
We consider the problem of routing in an asynchronous dynamically changing ring of processors using schemes that minimize the storage space for the routing information. In general, applying static...
Danny Krizanc, Sanguthevar Rajasekaran, Sunil M. Shende
We investigate the relative computational powers of a mesh with static buses and a mesh with half-duplex wrap-arounds. The latter model is like a torus, except that any wrap-around link of the...
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...
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...
Computing Minimum Spanning Trees with Uncertainty (2008)
Erlebach, Thomas, Hoffmann, Michael, Krizanc, Danny, Mihal'ák, Matús, Raman, Rajeev
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge $e$ of the graph only a set $A_e$, called...
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...
Hotlink Assignments, Danny Krizanc, Stefan Langerman, Pat Morin
We exhibit a relationship between the asymmetric communication problem of Adler and Maggs (1998) and the hotlink assignment problem of Bose et al (2000). By generalizing previous results on the...
Nordic Journal of Computing RANGE MODE AND RANGE MEDIAN QUERIES ON LISTS AND TREES ∗ (2008)
Danny Krizanc, Pat Morin, Michiel Smid
Abstract. We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of...
Strategies for Hotlink Assignments (Extended Abstract) Prosenjit Bose (2008)
Jurek Czyzowicz, Leszek G Asieniec, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc
\Lambda z
Computing Minimum Spanning Trees with Uncertainty (2008)
Erlebach, Thomas, Hoffmann, Michael, Krizanc, Danny, Mihal'ák, Matús, Raman, Rajeev
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge $e$ of the graph only a set $A_e$, called...
Computing Minimum Spanning Trees with Uncertainty (2008)
Erlebach, Thomas, Hoffmann, Michael, Krizanc, Danny, Mihal'ák, Matús, Raman, Rajeev
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge $e$ of the graph only a set $A_e$, called...
25. Computing Minimum Spanning Trees with Uncertainty (2008)
Hoffmann, Michael, Erlebach, Thomas, Krizanc, Danny, Mihal'ák, Matús, Raman, Rajeev
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge $e$ of the graph only a set $A_e$, called...
Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss, Godfried Toussaint
It is known that not all polygons in 3D can be convexied when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal...
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...
A Survey of Randomness and Parallelism in Comparison Problems (2007)
Abstract. A survey of results for the problems of selection, merging and sorting in the Randomized Parallel Comparison Tree (RPCT) model is given. The results indicate that while randomization \helps...
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...
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,...
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...
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...
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...
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, 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...
ENHANCING HYPERLINK STRUCTURE FOR IMPROVING WEB PERFORMANCE JUREK CZYZOWICZ (2007)
Danny Krizanc, Andrzej Pelc, Miguel Vargas Martin
In a Web site, each page v has a certain probability pv of being requested by a user. The access cost of a Web site is the sum of pv c(r; v), of every page v, where c(r; v) is the cost of the...
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...
Danny Krizanc, Stefan Langerman, Pat Morin
We exhibit a relationship between the asymmetric communication problem of Adler and Maggs (1998) and the hotlink assignment problem of Bose et al (2000). By generalizing previous results on the...
Jeannette Janssen, Danny Krizanc, Lata Narayanan, Sunil Shende
Abstract. In this paper, we develop a general framework for studying distributed online frequency assignment in cellular networks. The problem can be abstracted as a multicoloring problem on a...
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...
Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss, Godfried Toussaint
It is known that not all polygons in 3D can be convexied when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal...
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...
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,...
A Characterization of the Degree Sequences of 2-Trees (2006)
Bose, Prosenjit, Dujmović, Vida, Krizanc, Danny, Langerman, Stefan, Morin, Pat, Wood, David R., ...
A graph G is a 2-tree if G=K_3, or G has a vertex v of degree 2, whose neighbours are adjacent, and G\v{i}s a 2-tree. A characterization of the degree sequences of 2-trees is given. This...
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...
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES (2006)
Prosenjit Bose, Vida Dujmović, Danny Krizanc, Stefan Langerman, Pat Morin
ABSTRACT. A graph G is a 2-tree if G = K3, or G has a vertex v of degree 2, whose neighbours are adjacent, and G\v is a 2-tree. A characterization of the degree sequences of 2-trees is given. This...
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...
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...
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...
Range Mode and Range Median Queries on Lists and Trees (2003)
Krizanc, Danny, Morin, Pat, Smid, Michiel
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on...
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
Range mode and range median queries on lists and trees (2003)
Danny Krizanc, Pat Morin, Michiel Smid
ABSTRACT. We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of...
Range Mode and Range Median Queries on Lists and Trees (2003)
Danny Krizanc, Pat Morin, Michiel Smid
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on...
Range Mode and Range Median Queries on Lists and Trees (2003)
Danny Krizanc, Pat Morin, Michiel Smid
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on...
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...
Range Mode And Range Median Queries On Lists And Trees (2003)
Danny Krizanc Wesleyan, Danny Krizanc, Pat Morin, Michiel Smid
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on...
Range mode and range median queries on lists and trees (2003)
Danny Krizanc, Pat Morin, Michiel Smid
Abstract. We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of...
Optimal Assignment of Bookmarks to Web Pages (2002)
Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Miguel Vargas Martin
yzk
Asymmetric Communication Protocols Via Hotlink Assignments (2002)
Prosenjit Bose, Danny Krizanc, Stefan Langerman, Pat Morin
We exhibit a relationship between the asymmetric communication problem of Adler and Maggs (1998) and the hotlink assignment problem of Bose et al (2000). By generalizing previous results on the...
Asymmetric communication protocols via hotlink assignments (2002)
Prosenjit Bose, Danny Krizanc, Stefan Langerman, Pat Morin
Abstract. We exhibit a relationship between the asymmetric communication problem of Adler and Maggs (1998) and the hotlink assignment problem of Bose et al (2000). By generalizing previous results on...
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...
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
Convexifying Polygons with Simple Projections (2000)
Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss, Godfried Toussaint
It is known that not all polygons in 3D can be convexified when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal...
Station layouts in the presence of location constraints (1999)
Prosenjit Bose, Christos Kaklamanis, Lefteris M. Kirousis, Danny Krizanc, David Peleg
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:
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...
Approximating the unsatisfiability threshold of random formulas (1998)
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou
zx
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...
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...
Many-to-One Packet Routing via Matchings (1997)
In this paper we study the packet routing problem under the matching model proposed by Alon, Chung and Graham [1]. We extend the model to allow more than one packet per origin and destination node....
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...
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...
Multipacket Hot-Potato Routing on Processor Arrays (1996)
Christos Kaklamanis, Danny Krizanc
In this paper, we consider the problems of multipacket batch and balanced routing on d-dimensional (constant d 2) torus and meshconnected processor arrays. We present new "hot-potato"...
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...
Boolean Routing on Chordal Rings (1996)
Danny Krizanc, Flaminia L. Luccio
. In this paper we consider the problem of routing messages in a network of processors configured as a chordal ring. In particular we refer to the Boolean Routing model, and we introduce a new...
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...
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...
Zero-One Sorting On The Mesh (1995)
We consider the problem of sorting an input of size n 2 with keys restricted to the set f0; 1g on a n \Theta n mesh-connected computer. We present a deterministic algorithm that runs in 2:25n + o(n)...
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...
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...
Dietz, Paul, Krizanc, Danny, Rajasekaran, Sanguthevar, Shastri, Lokendra
In this paper we prove a lower bound of Ω(n log n) for the common element problem on two sets of size n each. Two interesting consequences of this lower bound are also discussed. In particular, we...
A Comparison Of Meshes With Static Buses and Unidirectional Wrap-Arounds (1992)
Krizanc, Danny, Rajasekaran, Sanguthevar, Shende, Sunil M.
We investigate the relative computational powers of a mesh with static buses and a mesh with unidirectional wrap-mounds. A mesh with unidirectional wraparounds is a torus with the restriction that...
A Note on Off-Line Permutation Routing on a Mesh-Connected Processor Array (1990)
We show how to off-line route any permutation of a n X n meshconnected processor array in 2.5n - 3 steps with at most 6 packets per processor per time step and in 2.25n +3 steps with at most 8...
Randomized Selection on the Mesh-Connected Processor Array (1990)
Krizanc, Danny, Narayanan, Lata
We show that selection on an input of size N = n2 can be performed by a N node mesh-connected processor array in 2n + o(n) steps, with high probability. The best previously known algorithm for this...
Integer Sorting on a Mesh-Connected Array of Processors (1990)
Schnorr and Shamir and independently Kunde, have shown that sorting N =n superscript 2 inputs into snake-like ordering on a n X n mesh requires 3n -o(n) steps. Using a less restrictive, more...
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...
Koeppel, Alexander, Perry, Elizabeth B., Sikorski, Johannes, Krizanc, Danny, Warner, Andrew, Ward, David M., ...
The central questions of bacterial ecology and evolution require a method to consistently demarcate, from the vast and diverse set of bacterial cells within a natural community, the groups playing...
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...
Christos Kaklamanis, Lefteris M. Kirousis, Danny Krizanc, David Peleg
Abstract. In wireless communication, the signal of a typical broadcast station is transmited from a broadcast center p and reaches objects at a distance, say, R from it. In addition there is a radius...