Robert W. Irving Rank-Maximal Matchings (2008)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna Paluch
Suppose that each member of a set ¡ of applicants ranks a subset of a set of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each...
An (O)over-tilde (m(2)n) Algorithm for Minimum Cycle Basis of Graphs (2008)
Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrios, Paluch, Katarzyna E
We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated...
Minimum Cycle Bases: Faster and Simpler (2008)
Kurt Mehlhorn, Dimitrios Michail
We consider the problem of computing exact or approximate minimum cycle bases of an undirected (or directed) edge-weighted graph G with m edges and n vertices. In this problem, a {0, 1} ({−1, 0,...
An Õ(m2 n) algorithm for Minimum Cycle Basis of graphs ∗ (2008)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch
We consider the problem of computing a minimum cycle basis in a graph G with m edges and n vertices. The input to this problem is an undirected graph whose edges have non-negative weights. In this...
Minimum Cycle Bases: Faster and Simpler (2008)
Kurt Mehlhorn, Dimitrios Michail
We consider the problem of computing exact or approximate minimum cycle bases of an undirected (or directed) edge-weighted graph G with m edges and n vertices. In this problem, a {0, 1} ({−1, 0,...
New approximation algorithms for minimum cycle bases of graphs (2007)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail
We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also...
New approximation algorithms for minimum cycle bases of graphs (2007)
Telikepalli Kavitha, Dimitrios Michail
Abstract. We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also...
New approximation algorithms for minimum cycle bases of graphs (2007)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail
We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this...
Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem (2007)
Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrios, Paluch, Katarzyna E.
Reducing rank-maximal to maximum weight matching (2007)
Given a bipartite graph G(V,E), where |V|=n,|E|=m and a partition of the edge set into r≤m disjoint subsets , which are called ranks, the rank-maximal matching problem is to find a matching M of G...
Implementing Minimum Cycle Basis Algorithms (2007)
Mehlhorn, Kurt, Michail, Dimitrios
In this paper, we consider the problem of computing a minimum cycle basis of an undirected graph G = (V,E) with n vertices and m edges. We describe an efficient implementation of an O(m3...
Cycle Bases of Graphs and Sampled Manifolds (2007)
Gotsman, Craig, Kaligosi, Kanela, Mehlhorn, Kurt, Michail, Dimitrios, Pyrga, Evangelia
New Approximation Algorithms for Minimum Cycle Bases of Graphs (2007)
Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrios
We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this...
Minimum cycle basis: algorithms and applications (2006)
Dimitrios Michail, Dekan Prof, Dr. René Beier, Στην Κανέλα
We consider the problem of computing a minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices. In this problem, a {0, 1} incidence vector is associated with each cycle...
Irving, Robert W., Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrios, Paluch, Katarzyna
Suppose that each member of a set A of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each...
Implementing Minimum Cycle Basis Algorithms (2006)
Mehlhorn, Kurt, Michail, Dimitrios
In this paper, we consider the problem of computing a minimum cycle basis of an undirected graph G = (V,E) with n vertices and m edges. We describe an efficient implementation of an O(m3...
Implementing Minimum Cycle Basis Algorithms (2005)
Kurt Mehlhorn, Dimitrios Michail
In this paper we consider the problem of computing a minimum cycle basis of an undirected graph G = (V, E) with n vertices and m edges. We describe an e#cient implementation of an O(m algorithm...
Network Problems with Non-Polynomial (2005)
Weights And Applications, Kurt Mehlhorn, Dimitrios Michail
The most e#cient algorithms for several network problems like minimum cost flow and the maximum weight matching problem follow the primal-dual paradigm. These algorithms perform arithmetic (additions...
Cycle Bases of Graphs and Sampled Manifolds (2005)
Craig Gotsman, Kanela Kaligosi, Kurt Mehlhorn, Dimitrios Michail, Evangelia Pyrga
... are the dominant output of a multitude of 3D scanning devices. The usefulness of these devices rests on being able to extract properties of the surface from the sample. We show that, under...
Cycle bases of graphs and sampled manifolds (2005)
Craig Gotsman, Kanela Kaligosi, Kurt Mehlhorn, Dimitrios Michail, Evangelia Pyrga
Point samples of a surface in R 3 are the dominant output of a multitude of 3D scanning devices. The usefulness of these devices rests on being able to extract properties of the surface from the...
Implementing minimum cycle basis algorithms (2005)
Kurt Mehlhorn, Dimitrios Michail
In this paper, we consider the problem of computing a minimum cycle basis of an undirected graph G = (V,E) with n vertices and m edges. We describe an efficient implementation of an O(m3 + mn2 log n)...
Implementing minimum cycle basis algorithms (2005)
Kurt Mehlhorn, Dimitrios Michail
In this paper we consider the problem of computing a minimum cycle basis of an undirected graph G = (V, E) with n vertices and m edges. We describe an efficient implementation of an O(m 3 + mn 2 log...
Implementing Minimum Cycle Basis Algorithms (2005)
Mehlhorn, Kurt, Michail, Dimitrios, Nikoletseas, Sotiris
In this paper we consider the problem of computing a minimum cycle basis of an undirected graph $G = (V,E)$ with $n$ vertices and $m$ edges. We describe an efficient implementation of an $O(m^3 +...
A Faster Algorithm for Minimum Cycle Basis of Graphs (2004)
Mehlhorn,Kurt, Michail,Dimitrios, Telikepalli,Kavitha, Paluch,Katarzyna
In this paper we consider the problem of computing a minimum cycle basis in a graph $G$ with $m$ edges and $n$ vertices. The edges of $G$ have non-negative weights on them. The previous best result...
Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents Problem (2004)
Mehlhorn, Kurt, Michail, Dimitrios, Telikepalli, Kavitha, Diekert, Volker, Habib, Michel
A Faster Algorithm for Minimum Cycle Basis of Graphs (2004)
Mehlhorn, Kurt, Michail, Dimitrios, Telikepalli, Kavitha, Paluch, Katarzyna, Díaz, Josep, Karhumäki, Juhani, ...
In this paper we consider the problem of computing a minimum cycle basis in a graph $G$ with $m$ edges and $n$ vertices. The edges of $G$ have non-negative weights on them. The previous best result...
Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna Paluch
Suppose that each member of a set�of applicants ranks a subset of a set Èof posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each...
A faster algorithm for minimum cycle basis of graphs (2004)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail
Abstract. In this paper we consider the problem of computing a minimum cycle basis in a graph G with m edges and n vertices. The edges of G have non-negative weights on them. The previous best result...
Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents Problem (2004)
Mehlhorn, Kurt, Michail, Dimitrios, Telikepalli, Kavitha, Diekert, Volker, Habib, Michel
A Faster Algorithm for Minimum Cycle Basis of Graphs (2004)
Mehlhorn, Kurt, Michail, Dimitrios, Telikepalli, Kavitha, Paluch, Katarzyna, Díaz, Josep, Karhumäki, Juhani, ...
In this paper we consider the problem of computing a minimum cycle basis in a graph $G$ with $m$ edges and $n$ vertices. The edges of $G$ have non-negative weights on them. The previous best result...
Strongly Stable Matchings in Time O(nm) (2003)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna Paluch
An instance of the stable marriage problem is an undirected bipartite graph G = (X [W;E) with linearly ordered adjacency lists; ties are allowed. A matching M is a set of edges no two of which share...