Show simple item record

dc.contributor.authorDereniowski, Dariusz*
dc.contributor.authorKubiak, W.*
dc.contributor.authorRies, Bernard*
dc.contributor.authorZwols, Yori*
dc.date.accessioned2013-06-18T07:49:43Z
dc.date.available2013-06-18T07:49:43Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11425
dc.language.isoenen
dc.subjectedge coloringen
dc.subjectfractional edge coloringen
dc.subjectnearly bipartite graphsen
dc.subjectscheduling algorithmsen
dc.subjectthroughput maximizationen
dc.subjectgreedy maximal schedulingen
dc.subjectwireless networksen
dc.subject.ddc004en
dc.titleOptimal edge-coloring with edge rate constraintsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence are computationally intractable. Therefore, as is commonly done [Golumbic, Algorithmic graph theory and perfect graphs, 2004], we restrict our investigation to a special class of graphs. In recent work [Birand et al., INFOCOM 2010 Proceedings, 2010], two of the authors dealt with so-called OLoP (Overall Local Pooling) graphs, a class of graphs for which similar matching-related problems are tractable (namely, in an online distributed wireless network scheduling setting). We therefore focus on these graphs and generalize the results to a larger class of graphs which we call GOLoP graphs. In particular, we show that deciding whether a given GOLoP graph has a matching sequence of length at most k can be done in linear time. In case the answer is affirmative, we show how to construct, in quadratic time, the matching sequence of length at most k. Finally, we prove that, for GOLoP graphs, the length of a shortest sequence does not exceed a constant times the least common denominator of the fractions r(e), leading to a pseudopolynomial-time algorithm for minimizing the length of the sequence. We show that the constant equals 1 for OLoP graphs and, following Seymour [Seymour, Proc. London Math. Soc., 1979], conjecture that the constant is as small as 2 for general graphs. We then show that this conjecture holds for all graphs with at most 10 vertices.en
dc.relation.isversionofjnlnameNetworks
dc.relation.isversionofjnlvol62
dc.relation.isversionofjnlissue3
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages165-182
dc.relation.isversionofdoi10.1002/net.21505en
dc.relation.isversionofjnlpublisherWileyen
dc.subject.ddclabelInformatique généraleen
dc.relation.forthcomingnonen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds*
hal.person.labIds*
hal.person.labIds989*
hal.person.labIds*
hal.identifierhal-01509690*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record