Show simple item record

dc.contributor.authorBentz, Cédric
dc.contributor.authorCosta, Marie-Christine
dc.contributor.authorRies, Bernard
dc.contributor.authorde Werra, Dominique
dc.contributor.authorPicouleau, Christophe
dc.contributor.authorZenklusen, Rico
dc.date.accessioned2011-04-22T13:56:22Z
dc.date.available2011-04-22T13:56:22Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6027
dc.language.isoenen
dc.subjectCaterpillaren
dc.subjectTreeen
dc.subjectGrid graphen
dc.subjectBlockeren
dc.subjectTransversalen
dc.subjectMatchingen
dc.subject.ddc511en
dc.titleBlockers and transversalsnext term in some previous termsubclasses of bipartite graphs: When caterpillars are dancing on a gridnext termen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherEPFL, Ecole Polytechnique Fédérale de Lausanne;Suisse
dc.contributor.editoruniversityotherUniversité Paris-Sud, LRI;France
dc.contributor.editoruniversityotherENSTA, UMA-CEDRIC;France
dc.contributor.editoruniversityotherETHZ, Eidgenössische Technische Hochschule Zürich;Suisse
dc.contributor.editoruniversityotherColumbia University;États-Unis
dc.contributor.editoruniversityotherCNAM, Laboratoire CEDRIC;France
dc.description.abstractenGiven an undirected previous termgraphnext term G=(V,E) with matching number ν(G), previous termanext term d-previous termblocker is anext term subset of edges B such that ν((V,Eset minusB))≤ν(G)−d and previous termanext term d-previous termtransversalnext term T is previous termanext term subset of edges such that every maximum matching M has |M∩T|≥d. While the associated decision problem is NP-complete in previous termbipartite graphsnext term we show how to construct efficiently minimum d-previous termtransversalsnext term and minimum d-previous termblockersnext term in the special cases where G is previous terma grid graph or anext term tree.en
dc.relation.isversionofjnlnameDiscrete Mathematics
dc.relation.isversionofjnlvol310en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages132-146en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.disc.2009.08.009en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen


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