Deferred on-line bipartite matching

2018
journal article
article
dc.abstract.enWe present a new model for the problem of on-line matching on bipartite graphs. Suppose that one part of a graph is given, but the vertices of the other part are presented in an on-line fashion. In the classical version, each incoming vertex is either irrevocably matched to a vertex from the other part or stays unmatched forever. In our version, an algorithm is allowed to match the new vertex to a group of elements (possibly empty). Later on, the algorithm can decide to remove some vertices from the group and assign them to another (just presented) vertex, with the restriction that each element belongs to at most one group. We present an optimal (deterministic) algorithm for this problem and prove that its competitive ratio equals.pl
dc.affiliationWydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznejpl
dc.contributor.authorKozik, Jakub - 129355 pl
dc.contributor.authorMatecki, Grzegorz - 130386 pl
dc.date.accession2018-05-11pl
dc.date.accessioned2018-05-15T11:28:44Z
dc.date.available2018-05-15T11:28:44Z
dc.date.issued2018pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number2pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume25pl
dc.identifier.articleidP2.24pl
dc.identifier.eissn1077-8926pl
dc.identifier.issn1097-1440pl
dc.identifier.projectUMO-2011/03/D/ST6/01370pl
dc.identifier.project2011/03/B/ST6/01367pl
dc.identifier.projectROD UJ / Ppl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/54311
dc.identifier.weblinkhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p24pl
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa - Bez utworów zależnych 4.0 Międzynarodowa*
dc.rights.licenceCC-BY-ND
dc.rights.urihttp://creativecommons.org/licenses/by-nd/4.0/legalcode.pl*
dc.share.typeotwarte czasopismo
dc.subject.enon-linepl
dc.subject.enbipartite matchingpl
dc.subject.enadaptive algorithmpl
dc.subtypeArticlepl
dc.titleDeferred on-line bipartite matchingpl
dc.title.journalThe Electronic Journal of Combinatoricspl
dc.typeJournalArticlepl
dspace.entity.typePublication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
0
Views per month