{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:22Z","timestamp":1740144502813,"version":"3.37.3"},"reference-count":16,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2020,1,15]],"date-time":"2020-01-15T00:00:00Z","timestamp":1579046400000},"content-version":"vor","delay-in-days":14,"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-13-BSH1-0010-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":[[2018,12,31]]},"published-print":{"date-parts":[[2020,1]]},"abstract":"Let G<\/jats:italic>\u00a0=\u00a0(N<\/jats:italic>,\u00a0E<\/jats:italic>,\u00a0w<\/jats:italic>) be a weighted communication graph. For any subset A<\/jats:italic>\u00a0\u2286\u00a0N<\/jats:italic>, we delete all minimum-weight edges in the subgraph induced by A<\/jats:italic>. The connected components of the resultant subgraph constitute the partition \ud835\udcabmin<\/jats:sub>(A<\/jats:italic>) of A<\/jats:italic>. Then, for every cooperative game (N<\/jats:italic>,\u00a0v<\/jats:italic>), the \ud835\udcabmin<\/jats:italic>-restricted game (N<\/jats:italic>, v\u0305<\/jats:italic>) is defined by v\u0305(A<\/jats:italic>)=\u2211F\u2208\ud835\udcabmin<\/jats:sub>(A<\/jats:italic>)<\/jats:sub>v(F<\/jats:italic>)\n for all A<\/jats:italic>\u00a0\u2286\u00a0N<\/jats:italic>. We prove that we can decide in polynomial time if there is inheritance of \u2131-convexity, i.e.<\/jats:italic>, if for every \u2131-convex game the \ud835\udcabmin<\/jats:sub>-restricted game is \u2131-convex, where \u2131-convexity is obtained by restricting convexity to connected subsets. This implies that we can also decide in polynomial time for any unweighted graph if there is inheritance of convexity for Myerson\u2019s graph-restricted game.<\/jats:p>","DOI":"10.1051\/ro\/2019003","type":"journal-article","created":{"date-parts":[[2019,1,3]],"date-time":"2019-01-03T19:45:47Z","timestamp":1546544747000},"page":"143-161","source":"Crossref","is-referenced-by-count":0,"title":["Complexity of inheritance of \u2131-convexity for restricted games induced by minimum partitions"],"prefix":"10.1051","volume":"54","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7148-3458","authenticated-orcid":false,"given":"A.","family":"Skoda","sequence":"first","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2020,1,15]]},"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":"Theor. 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","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":"R7","first-page":"405","volume":"33","author":"Faigle","year":"1989","journal-title":"Oper. Res."},{"key":"R8","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":"R9","unstructured":"Fujishige S., Submodular functions and optimization, 2nd edition. In Vol. 58 of Annals of Discrete Mathematics. Elsevier, (2005)."},{"key":"R10","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":"R11","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":"R12","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":"R13","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1051\/ro\/2017069","volume":"53","author":"Skoda","year":"2019","journal-title":"RAIRO: OR"},{"key":"R14","unstructured":"Skoda A., Inheritance of Convexity for the \ud835\udcabmin- Restricted Game. Documents de travail du Centre d\u2019Economie de la Sorbonne. ISSN : 1955-611X (2017)."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Skoda A., Inheritance of Convexity for the \ud835\udcabmin- Restricted Game (2018).","DOI":"10.1016\/j.disopt.2017.01.004"},{"key":"R16","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1007\/BF01766431","volume":"19","author":"van den Nouweland","year":"1991","journal-title":"Int. J. Game Theor."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2019003\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,20]],"date-time":"2020-03-20T07:30:25Z","timestamp":1584689425000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2019003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":16,"journal-issue":{"issue":"1"},"alternative-id":["ro180091"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2019003","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}