{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:17Z","timestamp":1740144497578,"version":"3.37.3"},"reference-count":18,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2019,6,28]],"date-time":"2019-06-28T00:00:00Z","timestamp":1561680000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-09- BLAN-0321-01"],"award-info":[{"award-number":["ANR-09- BLAN-0321-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2017,10,5]]},"published-print":{"date-parts":[[2019,7]]},"abstract":"<jats:p>We consider restricted games on weighted graphs associated with minimum partitions. We replace in the classical definition of Myerson restricted game the connected components of any subgraph by the sub-components corresponding to a minimum partition. This minimum partition \ud835\udcab<jats:sub>min<\/jats:sub> is i nduced by the deletion of the minimum weight edges. We provide five necessary conditions on the graph edge-weights to have inheritance of convexity from the underlying game to the restricted game associated with \ud835\udcab<jats:sub>min<\/jats:sub>. Then, we establish that these conditions are also sufficient for a weaker condition, called \u2131-convexity, obtained by restriction of convexity to connected subsets. Moreover, we prove that inheritance of convexity for Myerson restricted game associated with a given graph <jats:italic>G<\/jats:italic> is equivalent to inheritance of \u2131-convexity for the \ud835\udcab<jats:sub>min<\/jats:sub>-restricted game associated with a particular weighted graph <jats:italic>G\u2032<\/jats:italic> built from <jats:italic>G<\/jats:italic> by adding a dominating vertex, and with only two different edge-weights. Then, we prove that <jats:italic>G<\/jats:italic> is cycle-complete if and only if a specific condition on adjacent cycles is satisfied on <jats:italic>G\u2032<\/jats:italic>.<\/jats:p>","DOI":"10.1051\/ro\/2017069","type":"journal-article","created":{"date-parts":[[2017,10,6]],"date-time":"2017-10-06T07:08:08Z","timestamp":1507273688000},"page":"841-866","source":"Crossref","is-referenced-by-count":2,"title":["Convexity of graph-restricted games induced by minimum partitions"],"prefix":"10.1051","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7148-3458","authenticated-orcid":false,"given":"Alexandre","family":"Skoda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2019,6,28]]},"reference":[{"key":"R1","unstructured":"Algaba E., Extensi\u00f3n de juegos definidos en sistemas de conjuntos. Ph.D. thesis, Univ. of Seville (1998)."},{"key":"R2","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s001860000060","volume":"52","author":"Algaba","year":"2000","journal-title":"Math. Methods Oper. Res."},{"key":"R3","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1023\/A:1010344404281","volume":"50","author":"Algaba","year":"2001","journal-title":"Theory Decis."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Bilbao J.M., Cooperative games on combinatorial structures. Kluwer Academic Publishers, Boston (2000).","DOI":"10.1007\/978-1-4615-4393-0"},{"key":"R5","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1137\/S0895480102402745","volume":"17","author":"Bilbao","year":"2003","journal-title":"SIAM J. Discrete Math."},{"key":"R6","unstructured":"Borm P., Owen G. and Tijs S., Values of points and arcs in communication situations. Technical Report 9004, Dept of Mathematics, University of Nijmegen, The Netherlands (1990)."},{"key":"R7","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0167-5060(08)70734-9","volume":"1","author":"Edmonds","year":"1977","journal-title":"Ann. Discrete Math."},{"key":"R8","first-page":"405","volume":"33","author":"Faigle","year":"1989","journal-title":"Oper. Res."},{"key":"R9","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.ejor.2010.01.043","volume":"206","author":"Faigle","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"R10","unstructured":"Fujishige S., Submodular Functions and Optimization. Vol. 58 of Ann. Discrete Math. Elsevier, 2nd edition (2005)."},{"key":"R11","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s10479-012-1265-4","volume":"204","author":"Grabisch","year":"2013","journal-title":"Ann. Oper. Res."},{"key":"R12","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s10479-012-1200-8","volume":"201","author":"Grabisch","year":"2012","journal-title":"Ann. Oper. Res."},{"key":"R13","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1287\/moor.2.3.225","volume":"2","author":"Myerson","year":"1977","journal-title":"Math. Oper. Res."},{"key":"R14","unstructured":"Schrijver A., Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag (2003)."},{"key":"R15","unstructured":"Skoda A., Complexity of inheritance of \u2131-convexity for restricted games induced by minimum partitions. Documents de travail du Centre d\u2019Economie de la Sorbonne 2016.55 \u2013 ISSN: 1955-611X (2016)."},{"key":"R16","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1016\/j.disopt.2017.01.004","volume":"25","author":"Skoda","year":"2017","journal-title":"Discrete Optimiz."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Skoda A., Inheritance of Convexity for the \ud835\udcabmin-Restricted Game. Preprint Hal:halshs-01660670 (2017).","DOI":"10.1016\/j.disopt.2017.01.004"},{"key":"R18","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1007\/BF01766431","volume":"19","author":"van den Nouweland","year":"1991","journal-title":"Int. J. Game Theory"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2017069\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,20]],"date-time":"2020-03-20T07:41:36Z","timestamp":1584690096000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2017069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,28]]},"references-count":18,"journal-issue":{"issue":"3"},"alternative-id":["ro170091"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2017069","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2019,6,28]]}}}