Richard Cole, Shahar Dobzinski, Lisa Fleischer
Abstract. We study the following online problem: at each time unit, one of m identical items is offered for sale. Bidders arrive and depart dynamically, and each bidder is interested in winning one...
Two Dimensional Parameterized Matching (2009)
Richard Cole, Carmit Hazay, Moshe Lewenstein, Dekel Tsur
Two equal length strings, or two equal sized two-dimensional texts, parameterize match (p-match) if there is a one-one mapping (relative to the alphabet) of their characters. Two-dimensional...
[DB03] Datamation Benchmark. Sort Benchmark Home Page, hosted by Microsoft. (2008)
Acv Rajiv Wickremesinghe, Lars Arge, Jeff Chase, S. Vitter, ...
[AV88] ALOK AGGARWAL AND JEFFERY S. VITTER. The input/output complexity of sorting and related problems. Communications of the ACM, 1988.
Richard Cole, Bruce M. Maggs, Friedhelm Meyer, Heide Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
Multidimensional Matching and Fast Search in Suffix Trees (2008)
Richard Cole, Nyu Moshe Lewenstein
Abstract We show how to construct a suffix tree of a text string t in linear time, after sorting the characters in the text, so that a search for pattern p take time O(p + log t), independent of the...
A unified access bound on comparison-based dynamic dictionaries (2008)
Mihai Bădoiu, Richard Cole, Erik D. Demaine, John Iacono
We present a dynamic comparison-based search structure that supports insertions, deletions, and searches within the unified bound. The unified bound specifies that it is quick to access an element...
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-colton, Jack Zito Two
Advanced topics in data structures: bibliography list on string matching
A unified access bound on comparison-based dynamic dictionaries (2008)
Mihai Bădoiu, Richard Cole, Erik D. Demaine, John Iacono
We present a dynamic comparison-based search structure that supports insert, delete, and search within the unified bound. The unified bound specifies that it is quick to access an element that is...
Richard Cole, Bruce M. Maggst, Friedhelm Meyer, Heides Michael Mitzenmacher, Andrea W. Richat, Klaus Schrijderq
In tbis paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
ABSTRACT How Much Can Taxes Help Selfish Routing? (2008)
We study economic incentives for influencing selfish behavior in networks. We consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a...
Richard Cole, Thomas Tilley, Jon Ducrou, Richard Cole, Thomas Tilley, Jon Ducrou, ...
Abstract. Software systems are often highly structured, consisting of artifacts (types, methods, variables, and packages), and relationships between these artifacts. Domain models, meta models, and...
Richard Cole, Bruce M. Maggs, Friedhelm Meyer, Heide Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
1 Department of Computer Science, King's College London,
Fast-converging tatonnement algorithms for one-time and ongoing market problems (2008)
Why might markets tend toward and remain near equilibrium prices? In an effort to shed light on this question from an algorithmic perspective, this paper formalizes the setting of Ongoing Markets, by...
Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Andr'ea W. Richa, Ramesh K. Sitaraman, Eli Upfal
We consider the problem of extending the analysis of balls and bins processes to cover deletions. In particular, we are interested in the case where the system maintains a fixed load, and deletions...
Richard Cole, Ramesh Hariharan, Ramesh Hariharan
I cannot thank my advisor, Richard Cole, enough for his support and encouragement, for introducing me to the eld of string algorithms, for promptly and patiently reading the rather unreadable rst...
ABSTRACT How Much Can Taxes Help Selfish Routing? (2007)
Richard Cole, Yevgeniy Dodis, Tim Roughgarden
We study economic incentives for influencing selfish behavior in networks. We consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a...
CEM – Visualisation and Discovery in Email (2007)
Richard Cole, Peter Eklund, Gerd Stumme
Abstract. This paper presents a lattice-based visual metaphor for knowledge discovery in electronic mail. It allow a user to navigate email using a visual lattice metaphor rather than a tree...
Abstract. CEM is an email management system which stores its email in a concept lattice rather than in the usual tree structure. By using such a conceptual multi-hierarchy, the system provides more...
Fast Algorithms for Subset Matching and Tree Pattern Matching (2007)
Richard Cole, Ramesh Hariharan, Piotr Indyk
This paper describes an O(s log 3 s) time deterministic algorithm, an O(s log 3
Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick
The paper considers the exact number of character comparisons needed to nd all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line algorithms,...
Richard Cole, Zvi Galil, Ramesh Hariharan, S. Muthukrishnan
An optimal parallel CRCW-PRAM algorithm to compute witnesses for all non-period vectors of an m 1 m 2 pattern is given. The algorithm takes O(log log m) time and does O(m 1 m 2) work, where m = maxfm...
CONSTRUCTING CONCEPTUAL SCALES IN FORMAL CONCEPT ANALYSIS (2007)
Richard Cole, Peter Eklund, Don Walker
Abstract. Formal concept analysis (FCA) [2] is a technique for knowledge visualisation. Several software tools have been developed to aid knowledge exploration using FCA, the most prevelant of these...
Pricing Networks with Selfish Routing (2007)
Richard Cole Yevgen, Richard Cole, Yevgeniy Dodis, Tim Roughgarden
This paper surveys some of the results from two forthcoming conference papers [5, 6]
Pricing Networks with Selfish Routing (2007)
Richard Cole Yevgeniy, Richard Cole, Yevgeniy Dodis, Tim Roughgarden
This paper surveys some of the results from two forthcoming conference papers [5, 6]
Which Patterns Are Hard to Find? (2007)
Richard Cole, Ramesh Hariharan, Michael S. Paterson, Uri Zwick
The paper considers the exact number of character comparisons needed to find all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line...
Center for Mobility (DTRT06-G-0044). Table of Contents (2007)
David Schrank, Tim Lomax, Richard Cole, Rick Davenport, Bernie Fette, Michele Hoelscher—media Relations, ...
The contents of this report reflect the views of the authors, who are responsible for the facts and the accuracy of the information presented herein. This document is disseminated under the...
A Generalization of Kotzig's Theorem and Its Application (2007)
Cole, Richard, Kowalik, Lukasz, Skrekovski, Riste
An edge of a graph is light when the sum of the degrees of its end-vertices is at most 13. The well-known Kotzig theorem states that every 3-connected planar graph contains a light edge. Later,...
Automated Layout of Small Lattices Using Layer Diagrams (2006)
Richard Cole, Jon Ducrou, Peter Eklund
Abstract. Good quality concept lattice drawings are required to effectively communicate logical structure in Formal Concept Analysis. Data analysis frameworks such as the Toscana System use manually...
Bottleneck links, variable demand and the tragedy of the commons (2006)
Richard Cole, Yevgeniy Dodis, Tim Roughgarden
The price of anarchy, a measure of the inefficiency of selfish behavior, has been successfully analyzed in a diverse array of models over the past five years. The overwhelming majority of this work...
Towards Operational Abduction from a Cognitive Perspective (2006)
Abdul Bari, Zeeniya, Bruza, Peter, Cole, Richard, Song, Dawei
Towards Operational Abduction from a Cognitive Perspective (2006)
Abdul Bari, Zeeniya, Bruza, Peter, Cole, Richard, Song, Dawei
Towards Operational Abduction from a Cognitive Perspective (2006)
Abdul Bari, Zeeniya, Bruza, Peter, Cole, Richard, Song, Dawei
Towards Operational Abduction from a Cognitive Perspective (2006)
Bruza, Peter, Cole, Richard, Song, Dawei, Bari, Zeeniya
Diminishing awareness is a consequence of the information explosion: disciplines are becoming increasingly specialized; individuals and groups are becoming ever more insular. This article considers...
Towards Operational Abduction from a Cognitive Perspective (2006)
Abdul Bari, Zeeniya, Bruza, Peter, Cole, Richard, Song, Dawei
Dynamic LCA Queries on Trees (2005)
Cole, Richard, Hariharan, Ramesh
We show how to maintain a data structure on trees which allows for the following operations, all in worst-case constant time: 1. insertion of leaves and internal nodes, 2. deletion of leaves, 3....
Dynamic LCA Queries on Trees (2005)
Cole, Richard, Hariharan, Ramesh
We show how to maintain a data structure on trees which allows for the following operations, all in worst-case constant time: 1. insertion of leaves and internal nodes, 2. deletion of leaves, 3....
Bruza, Peter D., Cole, Richard
This article is an exploratory account of the the non-monotonic behaviour of conceptual associations in the light of context. Computational approximations of conceptual space are furnished by...
Bruza, Peter D., Cole, Richard
This article is an exploratory account of the the non-monotonic behaviour of conceptual associations in the light of context. Computational approximations of conceptual space are furnished by...
Bruza, Peter D., Cole, Richard
This article is an exploratory account of the the non-monotonic behaviour of conceptual associations in the light of context. Computational approximations of conceptual space are furnished by...
Bruza, Peter D., Cole, Richard
This article is an exploratory account of the the non-monotonic behaviour of conceptual associations in the light of context. Computational approximations of conceptual space are furnished by...
Navigation Spaces for the Conceptual Analysis of Software Structure (2005)
Abstract. Information technology of today is often concerned with information that is not only large in quantity but also complex in structure. Understanding this structure is important in many...
Bruza, Peter D., Cole, Richard
This article is an exploratory account of the the non-monotonic behaviour of conceptual associations in the light of context. Computational approximations of conceptual space are furnished by...
Bruza, Peter D., Cole, Richard
This article is an exploratory account of the the non-monotonic behaviour of conceptual associations in the light of context. Computational approximations of conceptual space are furnished by...
Concept learning and information inferencing on a highdimensional semantic space (2004)
Dawei Song, Peter Bruza, Richard Cole
How to automatically capture a significant portion of relevant background knowledge and keep it up-to-date has been a challenging problem encountered in current research on logic based information...
Faster Suffix Tree Construction with Missing Suffix Links (2003)
Cole, Richard, Hariharan, Ramesh
We consider suffix tree construction for situations with missing suffix links. Two examples of such situations are suffix trees for parameterized strings and suffix trees for two-dimensional arrays....
Tree Pattern Matching to Subset Matching in Linear Time (2003)
Cole, Richard, Hariharan, Ramesh
In this paper, we show an O(n+m) time Turing reduction from the tree pattern matching problem to another problem called the subset matching problem. Subsequent works have given efficient...
A Fast Algorithm for Computing Steiner Edge Connectivity (2003)
Cole, Richard, Hariharan, Ramesh
Given an undirected graph or an Eulerian directed graph G and a subset S of its vertices, we show how to determine the edge connectivity C of the vertices in S in time O(C3 n log n+m). This algorithm...
A Survey of Formal Concept Analysis Support for Software Engineering Activities (2003)
Thomas Tilley, Richard Cole, Peter Becker, Peter Eklund
Abstract. Formal Concept Analysis (FCA) has typically been applied in the field of software engineering to support software maintenance and object-oriented class identification tasks. This paper...
Browsing Semi-structured Texts on the web using Formal Concept Analysis. Web Intelligence (2003)
Richard Cole, Peter Eklund, Florence Amardeilh
Browsing unstructured Web-texts using Formal Concept Analysis (FCA) confronts two problems. Firstly, on-line Web-data is sometimes unstructured and any FCAsystem must include additional mechanisms to...
How much can taxes help selfish routing (2003)
Richard Cole, Yevgeniy Dodis, Tim Roughgarden
We study economic incentives for influencing selfish behavior in networks. We consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a...
Tree pattern matching to subset matching in linear time (2003)
Richard Cole, Ramesh Hariharan, An O
z This paper is the rst of two papers describing an O (npolylog(m)) time algorithm for the Tree Pattern Matching problem on a pattern of size m and a text of size n. In this paper, we show an O(n+m)...
A Survey of Formal Concept Analysis Support for Software Engineering Activities (2003)
Thomas Tilley, Richard Cole, Peter Becker, Peter Eklund
Formal Concept Analysis (FCA) has typically been applied in the field of software engineering to support software maintenance and object-oriented class identification tasks. This paper presents a...
Pricing Network Edges for Heterogeneous Selfish Users (2003)
Richard Cole, Yevgeniy Dodis, Tim Roughgarden
We study the negative consequences of selfish behavior in a congested network and economic means of influencing such behavior. We consider the model of selfish routing defined by Wardrop [30] and...
How Much Can Taxes Help Selfish Routing? (2003)
Richard Cole, Yevgeniy Dodis, Tim Roughgarden
networks. We consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a function of the edge congestion, and network users are assumed to...
How Much Can Taxes Help Selfish Routing? (2003)
Richard Cole, Yevgeniy Dodis, Tim Roughgarden
networks. We consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a function of the edge congestion, and network users are assumed to...
Querying and analysing document collections with formal concept analysis (2003)
Formal Concept Analysis (FCA) has been applied to the task of document retrieval in many different ways. In this paper we present a new document management tool, based on FCA and aimed at...
Pricing Network Edges for Heterogeneous Selfish Users (2003)
Richard Cole, Yevgeniy Dodis, Tim Roughgarden
We study the negative consequences of selfish behavior in a congested network and economic means of influencing such behavior. We consider a model of selfish routing in which the latency experienced...
A fast algorithm for computing steiner edge connectivity (2003)
Given an undirected graph or an Eulerian directed graph G and a subset S of its vertices, we show how to determine the edge connectivity C of the vertices in S in time O(C 3 n log n + m). This...
Tree pattern matching to subset matching in linear time (2003)
Richard Cole, Ramesh Hariharan
Abstract. In this paper, we show an O(n + m) time Turing reduction from the tree pattern matching problem to another problem calledthe subset matching problem. Subsequent works have given efficient...
Verifying Candidate Matches in Sparse and Wildcard Matching (2002)
Cole, Richard, Hariharan, Ramesh
This paper obtains the following results on pattern matching problems in which the text has length n and the pattern has length m. * An O(nlog m) time deterministic algorithm for the String Matching...
Verifying Candidate Matches in Sparse and Wildcard Matching (2002)
Cole, Richard, Hariharan, Ramesh
This paper obtains the following results on pattern matching problems in which the text has length n and the pattern has length m. * An O(nlog m) time deterministic algorithm for the String Matching...
Scanning and traversing: maintaining data for traversals in a memory hierarchy (2002)
Michael A. Bender, Richard Cole, Erik D. Demaine
Abstract. We study the problem of maintaining a dynamic ordered set subject to insertions, deletions, and traversals of k consecutive elements. This problem is trivially solved on a RAM and on a...
Structured ontology and information retrieval for email search and discovery (2002)
Abstract. This paper discusses an document discovery tool based on formal concept analysis. The program allows users to navigate email using a visual lattice metaphor rather than a tree. It...
Scanning and traversing: maintaining data for traversals in a memory hierarchy (2002)
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-coltony
Abstract. We study the problem of maintaining a dynamic ordered set subject to insertions, deletions, and traversals of k consecutive elements. This problem is trivially solved on a RAM and on a...
Exponential structures for efficient cache-oblivious algorithms (2002)
Michael A. Bender, Richard Cole, Rajeev Raman
Abstract. We present cache-oblivious data structures based upon exponential structures. These data structures perform well on a hierarchical memory but do not depend on any parameters of the...
Verifying candidate matches in sparse and wildcard matching (2002)
Richard Cole, Ramesh Hariharan
This paper obtains the following results on pattern matching problems in which the text has length n and the pattern has length m. An O(n log m) time deterministic algorithm for the String Matching...
Two simplified algorithms for maintaining order in a list (2002)
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, Jack Zito
In the Order-Maintenance Problem, the objective is to maintain a total order subject to insertions, deletions, and precedence queries. Known optimal solutions, due to Dietz and Sleator, are...
Two simplified algorithms for maintaining order in a list (2002)
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, Jack Zito
On Special Families of Morphisms Related to δ-Matching and Don't Care Symbols (2002)
Richard Cole, Costas Iliopoulos, Thierry Lecroq, Wojciech Plandowski, Wojciech Rytter
The delta-matching problem is a special version of approximate pattern-matching, motivated by applications in musical information retrieval, where the alphabet Sigma is an interval of integers. We...
Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy (2002)
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-colton
We study the problem of maintaining a dynamic ordered set subject to insertions, deletions, and traversals of k consecutive elements. This problem is trivially solved...
Two simplified algorithms for maintaining order in a list (2002)
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-colton, Jack Zito
Abstract. In the Order-Maintenance Problem, the objective is to maintain a total order subject to insertions, deletions, and precedence queries. Known optimal solutions, due to Dietz and Sleator, are...
A Faster Implementation of the Goemans-Williamson Clustering Algorithm (2001)
Cole, Richard, Hariharan, Ramesh, Lewenstein, Moshe, Porat, Ely
We give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting...
Amir, Amihood, Cole, Richard, Hariharan, Ramesh, Lewenstein, Moshe, Porat, Ely
We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and patterns are...
A Faster Implementation of the Goemans-Williamson Clustering Algorithm (2001)
Cole, Richard, Hariharan, Ramesh, Lewenstein, Moshe, Porat, Ely
We give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting...
Amir, Amihood, Cole, Richard, Hariharan, Ramesh, Lewenstein, Moshe, Porat, Ely
We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and patterns are...
Browsing semi-structured web texts using formal concept analysis (2001)
Abstract. Query-directed browsing of unstructured Web-texts using Formal Concept Analysis (FCA) confronts two problems. Firstly on-line Web-data is sometimes unstructured and any FCA-system must...
A Faster Implementation of the Goemans-Williamson Clustering Algorithm (2001)
Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat
We give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting...
Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat
We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and patterns are...
A Faster Implementation of the Goemans-Williamson Clustering Algorithm (2001)
Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat
We give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting...
Approximate String Matching: A Simpler Faster Algorithm (2000)
Cole, Richard, Hariharan, Ramesh
We give two algorithms for finding all approximate matches of a pattern in a text, where the edit distance between the pattern and the matching text substring is at most k. The first algorithm, which...
An O (n log n) algorithm for the maximum agreement subtree problem for binary trees (2000)
Cole, Richard, Farach-Colton, Martin, Hariharan, Ramesh, Przytycka, Teresa, Thorup, Mikkel
The maximum agreement subtree problem is the following. Given two rooted trees whose leaves are drawn from the same set of items (e.g., species), and the largest subset of these items so that the...
CEM - visualization and discovery in Email (2000)
Cole, Richard, Eklund, Peter, Stumme, Gerd
Auch erschienen in: Zighed, Djamel A. u.a. (Hrsg.): Principles of data mining and knowledge discovery. (Lecture notes in computer science ; 1910). Berlin u.a. : Springer, 2000. S. 367-374. ISBN...
CEM - a conceptual Email manager (2000)
Auch erschienen in: Ganter, Bernhard u.a. (Hrsg.): Conceptual structures. (Lecture notes in computer science ; 1867). Berlin u.a. : Springer, 2000. S. 438-452. ISBN 3-540-67859-X (The original...
Faster suffix tree construction with missing suffix links (2000)
Richard Cole, Ramesh Hariharan
We consider sux tree construction for situations with missing sux links. Two examples of such situations are sux trees for parameterized strings and sux trees for 2D arrays. These trees also have the...
CEM - a Conceptual Email Manager (2000)
Richard Cole, Gerd Stumme, Fachbereich Mathematik
Abstract. CEM is an email management system which stores its email in a concept lattice rather than in the usual tree structure. By using such a conceptual multi-hierarchy, the system provides more...
Recovering Structure from Unstructured Webaccessible Rental Classifieds (2000)
Richard Cole, Peter Eklund, Age Str
This paper describes a research prototype system called RFCA for structuring Web-accessible rental classified advertisements based on semantic content. A hand crafted parser is used to extract...
Automated Layout of Concept Lattices Using Force (2000)
Directed Placement And, Richard Cole
Concept lattices represent a conceptual hierarchy inherent in a data set. A labelled line diagram for such a lattice represents this information diagrammatically. A diagram for a concept lattice may...
Faster suffix tree construction with missing suffix links (2000)
Richard Cole, Ramesh Hariharan
Abstract. We consider suffix tree construction for situations with missing suffix links. Two examples of such situations are suffix trees for parameterized strings and suffix trees for...
CEM - visualization and discovery in Email (2000)
Cole, Richard, Eklund, Peter, Stumme, Gerd
Auch erschienen in: Zighed, Djamel A. u.a. (Hrsg.): Principles of data mining and knowledge discovery. (Lecture notes in computer science ; 1910). Berlin u.a. : Springer, 2000. S. 367-374. ISBN...
CEM - a conceptual Email manager (2000)
Auch erschienen in: Ganter, Bernhard u.a. (Hrsg.): Conceptual structures. (Lecture notes in computer science ; 1867). Berlin u.a. : Springer, 2000. S. 438-452. ISBN 3-540-67859-X (The original...
Dynamic LCA queries on trees (1999)
Richard Cole, Ramesh Hariharan
Abstract. We show how to maintain a data structure on trees which allows for the following operations, all in worst-case constant time: 1. insertion of leaves and internal nodes, 2. deletion of...
Dynamic LCA queries on trees (1999)
Richard Cole, Ramesh Hariharan
We show how to maintain a data structure on trees which allows for the following operations, all in worst-case constant time. 1. Insertion of leaves and internal nodes. 2. Deletion of leaves. 3....
Comic Strips for Algorithm Visualization (1999)
Henning Biermann, Richard Cole
This paper presents visualizations of binary search trees and splay trees. The visualizations comprise sequences of figures or frames, called comic strips. Consecutive frames are viewed two at a time...
Scalability in formal concept analysis (1999)
Formal Concept Analysis is a symbolic learning technique derived from mathematical algebra and order theory. The technique has been applied to a broad range of knowledge representation and...
Scalability in formal concept analysis (1999)
Formal Concept Analysis is a symbolic learning technique derived from mathematical algebra and order theory. The technique has been applied to a broad range of knowledge representation and...
The Application of Formal Concept Analysis to Document Sources (1999)
The aim of the project is to nd a scalable mechanism by which the data anlysis technique of formal concept analysis (FCA) can be applied to information captured from a large corpus of text data....
Edge-Coloring Bipartite Multigraphs in O(E log D) Time (1999)
Richard Cole, Kirstin Ost, Stefan Schirra
Let V , E, and D denote the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G. We show that a minimal edge-coloring of G can be...
Randomized Swap Matching in O(m log m log |Sigma|) time (1999)
Richard Cole, Ramesh Hariharan
We give a randomized algorithm for the Pattern Matching with Swaps problem which runs in O(m log m log jj) time on a text of length 2m 1 and a pattern of length m drawn from an alphabet set of size...
Comic Strips for Algorithm Visualization (1999)
Henning Biermann, Richard Cole
This paper presents visualizations of binary search trees and splay trees. The visualizations comprise sequences of figures or frames, called comic strips. Consecutive frames are viewed two at a time...
Analyzing an Email Collection Using Formal Concept Analysis (1999)
this paper attempts to strike a middle road allowing the user to construct and modify scales in response to learning information about the data. It is novel in that it allows the user to de ne a...
Tree pattern matching and subset matching in deterministic O(n log3 n)-time (1999)
Richard Cole, Ramesh Hariharan, Piotr Indyk
Tree pattern matching and subset matching in deterministic O(n log
Approximate String Matching: A Simpler Faster Algorithm (1998)
Richard Cole, Ramesh Hariharan
Abstract. We give two algorithms for finding all approximate matches of a pattern in a text, where the edit distance between the pattern and the matching text substring is at most k. The first...
On Balls and Bins with Deletions (1998)
Richard Cole, Alan Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Ramesh Sitaraman, ...
Microsystems. The views and conclusions contained here are those of the authors and should not be interpreted as necessarily representing the official policies or
Using Conceptual Scaling in Formal Concept Analysis for Knowledge and Data Discovery (1998)
Richard Cole, Richard Cole, Peter Eklund, Peter Eklund, Don Walker, Don Walker
Formal concept analysis (FCA) [10] is a technique for knowledge representation and unsupervised machine learning that has been applied to a wide variety of knowledge representation and exploration...
Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
On Balls and Bins with Deletions (1998)
Richard Cole, Alan Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Andr'ea W. Richa, ...
We consider the problem of extending the analysis of balls and bins processes where a ball is placed in the least loaded of d randomly chosen bins to cover deletions. In particular, we are interested...
Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Friedhelm Meyer, Heide Michael Mitzenmacher, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
Tighter upper bounds on the exact complexity of string matching (1997)
Cole, Richard, Hariharan, Ramesh
This paper considers how many character comparisons are needed to nd all occurrences of a pattern of length m in a text of length n. The main contribution is to show an upper bound of the form of n +...
Tree Pattern Matching and Subset Matching in Randomized O(n log³ m) Time (1997)
Richard Cole, Ramesh Hariharan
The main goal of this paper is to give an efficient algorithm for the Tree Pattern Matching problem. We also introduce and give an efficient algorithm for the Subset Matching problem. The Subset...
Dealing With Large Contexts in Formal Concept Analysis: A Case Study Using Medical Texts (1997)
Richard Cole, Peter Eklund, Bernd Groh
. Formal concept analysis (FCA) was proposed by Wille in 1982[1]. and has been applied to a wide variety of knowledge representation and exploration tasks in a range of disciplines including civil...
Tighter upper bounds on the exact complexity of string matching (1997)
Richard Cole, Ramesh Hariharan
Abstract. This paper considers how many character comparisons are needed to find all occurrences of a pattern of length m in a text of length n. The main contribution is to show an upper bound of the...
An O(n log n) algorithm for the maximum agreement subtree problem for binary trees (1996)
Richard Cole, Martin Farach-colton, Ramesh Hariharan, Teresa Przytycka, Mikkel Thorup
Abstract. The maximum agreement subtree problem is the following. Given two rooted trees whose leaves are drawn from the same set of items (e.g., species), find the largest subset of these items so...
An O(n log n) algorithm for the maximum agreement subtree problem for binary trees (1996)
Richard Cole, Martin Farach-colton, Ramesh Hariharan, Mikkel Thorup
Abstract. The Maximum Agreement Subtree problem is the following: given two rooted trees whose leaves are drawn from the same set of items (e.g., species), find the largest subset of these items so...
An O(n log n) algorithm for the maximum agreement subtree problem for binary trees (1996)
Richard Cole, Martin Farach, Ramesh Hariharan, Teresa Przytycka, Mikkel Thorup
The Maximum Agreement Subtree problem is the following: given two trees whose leaves are drawn from the same set of items (e.g., species), find the largest subset of these items so that the portions...
Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling (1996)
Richard Cole, Philip N. Klein, Robert E. Tarjan
We describe a randomized CRCW PRAM algorithm that finds a minimum spanning forest of an n-vertex graph in O(log n) time and linear work. This shaves a factor of 2 log n off the best previous running...
On the Benefit of Supporting Virtual Channels in Wormhole Routers (1996)
Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman
This paper analyzes the impact of virtual channels on the performance of wormhole routing algorithms. We show that in any network in which each physical channel, i.e., communication link, can support...
On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences (1995)
Richard Cole, Bud Mishra, Jeanette Schmidt, Alan Siegel
A special case of the Dynamic Finger Conjecture is proved; this special case introduces a number of useful techniques. 1 Introduction The splay tree is a self-adjusting binary search tree devised by...
Tighter Lower Bounds on the Exact Complexity of String Matching (1995)
Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick
. The paper considers the exact number of character comparisons needed to find all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line...
A Linear-Work Parallel Algorithm for Finding Minimum Spanning Trees (1994)
Richard Cole, Philip N. Klein, Robert E. Tarjan, Philip N, Robert E
We give the first linear-work parallel algorithm for finding a minimum spanning tree. It is a randomized algorithm, and requires O(2 log 3 n log n) expected time. It is a modification of the...
Richard Cole, Maxime Crochemore, Zvi Galil, Leszek Gasieniec, Ramesh Hariharan, S. Muthukrishnan, ...
All algorithms below are optimal alphabet-independent parallel CRCW PRAM algorithms. In one dimension: Given a pattern string of length m for the string-matching problem, we design an algorithm that...
I.B.Turksen,Intervalvaluedfuzzysetsand`compensatoryand', Fuzzy Sets and Systems 51 (1992)
This paper discusses an email discovery and information retrieval tool based on formal concept analysis. The program allows users to navigate email using a visual lattice metaphor rather than a tree....
Randomized Parallel Algorithms For Trapezoidal Diagrams (1992)
Kenneth L. Clarkson, Richard Cole, Robert E. Tarjan
We describe randomized parallel algorithms for building trapezoidal diagrams of line segments in the plane. The algorithms are designed for a CRCW PRAM. For general segments, we give an algorithm...
A new general parallel algorithmic technique for computations on trees is presented. The new technique performs a reduction of the tree expression evaluation problem to list ranking; then, the list...
An Optimal Selection Algorithm (1986)
We give an optimal parallel algorithm for selection on the EREW PRAM. It requires a linear number of operations and O(log n log* n) time.
The relationship between graph isomorphism and graph rigidity is studied. Although in general it is not known if these problems are equivalent under polynomial time Turing reductions, equivalence is...
On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
The following result is shown: On an n-node splay tree, the amortized cost of an access at distance d from the preceding access is O(log(d + 1)). In addition, there is an O(n) initialization cost....