[{"uri_base":"https://research-explorer.ista.ac.at","conference":{"name":"MFCS: Mathematical Foundations of Computer Science"},"extern":1,"day":"09","quality_controlled":0,"publication_status":"published","main_file_link":[{"open_access":"0","url":"http://arxiv.org/pdf/1007.1229v3"}],"dc":{"creator":["Vladimir Kolmogorov"],"description":["We introduce a new class of functions that can be minimized in polynomial time in the value oracle model. These are functions f satisfying f(x) + f(y) ≥ f(x ∏ y) + f(x ∐ y) where the domain of each variable x i corresponds to nodes of a rooted binary tree, and operations ∏,∐ are defined with respect to this tree. Special cases include previously studied L-convex and bisubmodular functions, which can be obtained with particular choices of trees. We present a polynomial-time algorithm for minimizing functions in the new class. It combines Murota's steepest descent algorithm for L-convex functions with bisubmodular minimization algorithms. "],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"source":["Kolmogorov V. Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions. In: Vol 6907. Springer; 2011:400-411. doi:10.1007/978-3-642-22993-0_37"],"title":["Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions","LNCS"],"identifier":["https://research-explorer.ista.ac.at/record/3204"],"rights":["info:eu-repo/semantics/closedAccess"],"date":["2011"],"publisher":["Springer"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-22993-0_37"]},"volume":6907,"page":"400 - 411","alternative_title":[],"date_published":"2011-08-09T00:00:00Z","intvolume":" 6907","dini_type":"doc-type:conferenceObject","citation":{"ista":"Kolmogorov V. 2011. Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions. MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 6907, 400–411.","chicago":"Kolmogorov, Vladimir. “Submodularity on a Tree: Unifying Submodularity on a Tree: Unifying L-Convex and Bisubmodular Functions Convex and Bisubmodular Functions,” 6907:400–411. Springer, 2011. https://doi.org/10.1007/978-3-642-22993-0_37.","mla":"Kolmogorov, Vladimir. Submodularity on a Tree: Unifying Submodularity on a Tree: Unifying L-Convex and Bisubmodular Functions Convex and Bisubmodular Functions. Vol. 6907, Springer, 2011, pp. 400–11, doi:10.1007/978-3-642-22993-0_37.","apa":"Kolmogorov, V. (2011). Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions (Vol. 6907, pp. 400–411). Presented at the MFCS: Mathematical Foundations of Computer Science, Springer. https://doi.org/10.1007/978-3-642-22993-0_37","ieee":"V. Kolmogorov, “Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions,” presented at the MFCS: Mathematical Foundations of Computer Science, 2011, vol. 6907, pp. 400–411.","short":"V. Kolmogorov, in:, Springer, 2011, pp. 400–411."},"abstract":[{"lang":"eng"}],"status":"public","publist_id":"3478","_id":"3204","author":[{"first_name":"Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"month":"08","date_updated":"2021-01-12T07:41:47Z","type":"conference","date_created":"2018-12-11T12:02:00Z"}]