Computability of width of submodular partition functions

DOI10.1016/J.EJC.2011.12.010MaRDI QIDQ1933647zbMATH OpenOpenAlexFDO

Authors Petr Škoda

Publication date 24 January 2013

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2011.12.010

zbMATH Keywords

branch-widthtree-width

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Computability of width of submodular partition functions
• scientific article; zbMATH DE number 176870
• Submodular partition functions
• Computing and Combinatorics
• On complexity of maximizatin of submodular functions^*
• On the computational complexity of (O,P)-partition problems
• New approximations and hardness results for submodular partitioning problems
• Computing partial hypergraphs of bounded width
• Parameterized (in)approximability of subset problems
• Separating Sublinear Time Computations by Approximate Diameter

Cited in

(2)

• Submodular partition functions
• Computability of width of submodular partition functions

This page was built for publication: Computability of width of submodular partition functions

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