Submodular functions and rooted trees

DOI10.1007/S00224-022-10092-XMaRDI QIDQ2095463zbMATH OpenOpenAlexFDO

Authors Yaokun Wu, Yinfeng Zhu

Publication date 16 November 2022

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-022-10092-x

zbMATH Keywords

weighted hypergraphpseudorandom graphanticore\((\alpha, \beta)\) down-setBBT spanning tree

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorics of partially ordered sets (06A07)

Recommendations

• Submodular functions and independence structures
• scientific article; zbMATH DE number 4099306
• scientific article; zbMATH DE number 4083365
• A tree version of Kőnig's theorem
• K-submodular functions and convexity of their Lovász extension

Cites work

• scientific article; zbMATH DE number 3165195 (Why is no real title available?)
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 3505964 (Why is no real title available?)
• scientific article; zbMATH DE number 1234397 (Why is no real title available?)
• scientific article; zbMATH DE number 1055778 (Why is no real title available?)
• scientific article; zbMATH DE number 1099359 (Why is no real title available?)
• scientific article; zbMATH DE number 1113187 (Why is no real title available?)
• scientific article; zbMATH DE number 1748069 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A Dual of Dilworth's Decomposition Theorem
• A characterization of perfect graphs
• A decomposition theorem for partially ordered sets
• A double look at duality
• A new class of convex games on \(\sigma\)-algebras and the optimal partitioning of measurable spaces
• A new notion of convexity in digraphs with an application to Bayesian networks
• A note on weighted rooted trees
• A simple proof for the convexity of the Choquet integral
• Algebraic duality theorems for infinite LP problems
• An introduction to measure theory
• Blocking duality for \(p\)-modulus on networks and applications
• Combinatorial geometries, convex polyhedra, and Schubert cells
• Combinatorial representation and convex dimension of convex geometries
• Connectivity functions and polymatroids
• Convex games with an infinite number of players and sequencing situations
• Cores of convex games
• Cores of exact games. I
• Countably additive measures in cores of games
• Decomposing a balanced game: a necessary and sufficient condition for the nonemptiness of the core
• Discrete Convex Analysis
• Extremal problems for finite sets
• Extreme points of a set of contents majorized by a submodular set function
• Finitely Additive Measures
• Gomory‐Hu trees of infinite graphs with finite total weight
• Higher order Fourier analysis
• History of Banach Spaces and Linear Operators
• Homomorphisms and Ramsey properties of antimatroids
• Last passage percolation on the complete graph
• Maharam's problem
• Nombre chromatique et plus longs chemins d'un graphe
• Order- and graph-theoretic investigation of dimensions of finite topological spaces and Alexandroff spaces
• Partial probabilistic information
• Phylogenetic flexibility via Hall-type inequalities and submodularity
• Polymatroidal dependence structure of a set of random variables
• Representation of lattices via set-colored posets
• Set functions, games and capacities in decision making
• Some remarks on the discrete uncertainty principle
• The Erdős-Hajnal conjecture for long holes and antiholes
• The Generic Chaining
• The concept of duality in convex analysis, and the characterization of the Legendre transform
• The sigma-core of a cooperative game
• The sigma-core of convex games and the problem of measure extension
• The size Ramsey number of a directed path
• Theory of capacities
• Three conjectures of Ostrander on digraph Laplacian eigenvectors
• Trees as semilattices
• Uncertainty relation for multidimensional discrete signals
• Weighted Rooted Trees: Fat or Tall?
• Wurzelbäume und unendliche Wege in Graphen

Cited in

(1)

• Submodular unsplittable flow on trees

This page was built for publication: Submodular functions and rooted trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2095463)