A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem (2008)
Paluch, Katarzyna, Mucha, Marcin, Madry, Aleksander
We give a 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem.
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...
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...
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...
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)
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...