Constrained matchings in bipartite graphs

Andrea Borghesan (), Daniela Favaretto () and Francesco Mason
Additional contact information
Andrea Borghesan: Department of Management, Università Ca' Foscari Venezia
Daniela Favaretto: Department of Management, Università Ca' Foscari Venezia

No 22, Working Papers from Venice School of Management - Department of Management, Università Ca' Foscari Venezia

Abstract: We consider some particular cases of the general problem which consists of stating if a shift vector of m elements corresponds to a permutation of the same number of objects. Shifts are defined as the steps each element in a given permutation must perform in order to reach its natural position, i.e., to its position in the fundamental permutation, (1, 2, ... , m). The problem, never studied at our knowledge, was suggested to us by a paper in which a certain number of vehicles must be moved from initial to nal positions in a grid graph in such a way that vehicles do not share the same vertex at the same time. The problem can also be stated in terms of a covering one, i.e. the vertex cover of a particular graph, with cycle using arcs of de ned lengths. Some properties of the shift vector, necessary in order to guarantee the existence of a corresponding permutation, and a general algorithm to find the permutations, if they exist, are given.

Keywords: Cycle covering; Permutations (search for similar items in EconPapers)
JEL-codes: C61 C63 (search for similar items in EconPapers)
Pages: 14 pages
Date: 2012-11
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://virgo.unive.it/wpideas/storage/2012wp22.pdf First version, 2012 (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to virgo.unive.it:80 (A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond.)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:vnm:wpdman:35

Access Statistics for this paper

More papers in Working Papers from Venice School of Management - Department of Management, Università Ca' Foscari Venezia Contact information at EDIRC.
Bibliographic data for series maintained by Daria Arkhipova ().