Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Irving, Robert W.
Telikepalli, Kavitha
Mehlhorn, Kurt
Michail, Dimitrios
Paluch, Katarzyna		dblp
dblp
dblp
dblp
dblp
Not MPG Author(s):
Irving, Robert W.
Telikepalli, Kavitha
Paluch, Katarzyna

BibTeX cite key*:

ITMMP2006

Title

Title*:

Rank-Maximal Matchings

Journal

Journal Title*:

ACM Transactions on Algorithms
Journal's URL:

http://www.acm.org/talg/

Download URL
for the article:

http://delivery.acm.org/10.1145/1200000/1198520/p602-irving.pdf?key1=1198520&key2=2915073711&coll=ACM&dl=ACM&CFID=15151515&CFTOKEN=6184618
Language:

English

Publisher

Publisher's
Name:

ACM
Publisher's URL:


Publisher's
Address:

New York, USA
ISSN:


Vol, No, pp, Date

Volume*:

2
Number:

4

Publishing Date:

October 2006

Pages*:

602-610
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:

10.1145/1198513.1198520

Note, Abstract, ©

Note:


(LaTeX) Abstract:

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 applicant and each post appears in at most one pair. A rank-maximal matching is one in which the maximum possible number of applicants are matched to their first choice post, and subject to that condition, the maximum possible number are matched to their second choice post, and so on. This is a relevant concept in any practical matching situation and it was first studied by Irving [2003].We give an algorithm to compute a rank-maximal matching with running time O(min(n + C,C√n)m), where C is the maximal rank of an edge used in a rank-maximal matching, n is the number of applicants and posts and m is the total size of the preference lists.

URL for the Abstract:

http://portal.acm.org/citation.cfm?id=1198513.1198520&coll=ACM&dl=ACM&idx=J982&part=periodical&WantType=periodical&title=ACM%20Transactions%20on%20Algorithms%20(TALG)&CFID=15151515&CFTOKEN=6184618

Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{ITMMP2006,
AUTHOR = {Irving, Robert W. and Telikepalli, Kavitha and Mehlhorn, Kurt and Michail, Dimitrios and Paluch, Katarzyna},
 TITLE = {Rank-Maximal Matchings},
 JOURNAL = {ACM Transactions on Algorithms},
 PUBLISHER = {ACM},
 YEAR = {2006},
 NUMBER = {4},
 VOLUME = {2},
 PAGES = {602--610},
 ADDRESS = {New York, USA},
 MONTH = {October},
 DOI = {10.1145/1198513.1198520},
}

Entry last modified by Anja Becker, 01/07/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Dimitrios Michail		Created
02/26/2007 12:13:22
Revisions
7.
6.
5.
4.
3.		Editor(s)
Anja Becker
Christine Kiesel
Uwe Brahm
Uwe Brahm
Uwe Brahm		Edit Dates
07.01.2008 10:34:29
02.05.2007 14:21:31
2007-04-27 13:19:56
04/10/2007 07:12:40 PM
12.03.2007 14:14:29