Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Michail, Dimitrios

dblp



BibTeX cite key*:

Dimitrios2007

Title

Title*:

Reducing rank-maximal to maximum weight matching

Journal

Journal Title*:

Theoretical Computer Science

Journal's URL:


Download URL
for the article:

http://dx.doi.org/10.1016/j.tcs.2007.08.004

Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:


Publisher's
Address:

Amsterdam, The Netherlands

ISSN:

0304-3975

Vol, No, pp, Date

Volume*:

389

Number:

1-2

Publishing Date:

December 2007

Pages*:

125-132

Number of
VG Pages:


Page Start:

125

Page End:

132

Sequence Number:


DOI:

10.1016/j.tcs.2007.08.004

Note, Abstract, ©

Note:


(LaTeX) Abstract:

Given a bipartite graph G(V,E), Click to view the MathML sourcewhere |V|=n,|E|=m and a partition of the edge set into r≤m disjoint subsets Click to view the MathML source, which are called ranks, the rank-maximal matching problem is to find a matching M of G such that |M∩E1| is maximized and given that |M∩E1| is maximized, |M∩E2| is also maximized, and so on. Such a problem arises as an optimization criteria over a possible assignment of a set of applicants to a set of posts. The matching represents the assignment and the ranks on the edges correspond to a ranking of the posts submitted by the applicants.

The rank-maximal matching problem and several other optimization variants, e.g. fair matching and maximum cardinality rank-maximal matching, can be solved by a reduction to the weight matching problem in time Click to view the MathML source. Recently, Irving et al. developed a combinatorial approach which improves the running time for the rank-maximal matching problem to Click to view the MathML source. They raised the open questions on (a) whether such a running time can be achieved by the weight matching reduction and (b) whether such a running time can be achieved for the other variants of the problem.

In this work we show how the reduction to the weight matching problem can also be used to achieve the same running time. Our algorithm is simpler and more intuitive.


URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Dimitrios2007,
AUTHOR = {Michail, Dimitrios},
TITLE = {Reducing rank-maximal to maximum weight matching},
JOURNAL = {Theoretical Computer Science},
PUBLISHER = {Elsevier},
YEAR = {2007},
NUMBER = {1-2},
VOLUME = {389},
PAGES = {125--132},
ADDRESS = {Amsterdam, The Netherlands},
MONTH = {December},
ISBN = {0304-3975},
DOI = {10.1016/j.tcs.2007.08.004},
}


Entry last modified by Anja Becker, 02/28/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)
Anja Becker
Created
02/14/2008 12:27:24 PM
Revision
0.



Editor
Anja Becker



Edit Date
14.02.2008 12:29:47



Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section