{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T17:05:16Z","timestamp":1709831116896},"reference-count":5,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p> Given a system (V, f, r) on a finite set V consisting of a posi-modular function f : 2<jats:sup>V<\/jats:sup> \u2192 \u211d and a modulotone function r : 2<jats:sup>V<\/jats:sup> \u2192 \u211d, we consider the problem of finding a minimum set R \u2286 V such that f(X) \u2265 r(X) for all X \u2286 V - R. The problem, called the transversal problem, was introduced in [M. Sakashita, K. Makino, H. Nagamochi and S. Fujishige, Minimum transversals in posi-modular systems, SIAM J. Discrete Math.23 (2009) 858\u2013871] as a natural generalization of the source location problem and external network problem with edge-connectivity requirements in undirected graphs and hypergraphs. <\/jats:p><jats:p> By generalizing [H. Tamura, H. Sugawara, M. Sengoku and S. Shinoda, Plural cover problem on undirected flow networks, IEICE Trans.J81-A (1998) 863\u2013869] for the source location problem, we show that the transversal problem can be solved by a simple greedy algorithm if r is \u03c0-monotone, where a modulotone function r is \u03c0-monotone if there exists a permutation \u03c0 of V such that the function p<jats:sub>r<\/jats:sub>: V \u00d7 2<jats:sup>V<\/jats:sup> \u2192 \u211d associated with r satisfies p<jats:sub>r<\/jats:sub>(u, W) \u2265 p<jats:sub>r<\/jats:sub>(v, W) for all W \u2286 V and u, v \u2208 V with \u03c0(u) \u2265 \u03c0(v). Here we show that any modulotone function r can be characterized by p<jats:sub>r<\/jats:sub> as r(X) = max {p<jats:sub>r<\/jats:sub>(v, W) | v \u2208 X \u2286 V - W}. <\/jats:p><jats:p> We also show the structural properties on the minimal deficient sets [Formula: see text] for the transversal problem for \u03c0-monotone function r, i.e., there exists a basic tree T for [Formula: see text] such that \u03c0(u) \u2264 \u03c0(v) for all arcs (u,v) in T, which, as a corollary, gives an alternative proof for the correctness of the greedy algorithm for the source location problem. <\/jats:p><jats:p> Furthermore, we show that a fractional version of the transversal problem can be solved by the algorithm similar to the one for the transversal problem. <\/jats:p>","DOI":"10.1142\/s1793830910000474","type":"journal-article","created":{"date-parts":[[2010,4,20]],"date-time":"2010-04-20T05:35:00Z","timestamp":1271741700000},"page":"61-76","source":"Crossref","is-referenced-by-count":2,"title":["POSI-MODULAR SYSTEMS WITH MODULOTONE REQUIREMENTS UNDER PERMUTATION CONSTRAINTS"],"prefix":"10.1142","volume":"02","author":[{"given":"TOSHIMASA","family":"ISHII","sequence":"first","affiliation":[{"name":"Department of Information and Management Science, Otaru University of Commerce, Otaru 047-8501, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KAZUHISA","family":"MAKINO","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science and Technology, University of Tokyo, Tokyo 113-8656, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1203"},{"key":"rf5","first-page":"704","volume":"83","author":"Ito H.","journal-title":"IEICE Trans. E"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1137\/060663970"},{"key":"rf7","first-page":"678","volume":"75","author":"Tamura H.","journal-title":"IEICE Trans."},{"key":"rf8","first-page":"863","volume":"81","author":"Tamura H.","journal-title":"IEICE Trans."}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830910000474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T21:23:12Z","timestamp":1565126592000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830910000474"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":5,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1142\/S1793830910000474"],"URL":"https:\/\/doi.org\/10.1142\/s1793830910000474","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3]]}}}