Upper Bounds on Boolean-Width with Applications to Exact Algorithms

DOI10.1007/978-3-319-03898-8_26MaRDI QIDQ2867092zbMATH OpenOpenAlexFDO

Authors Yuri Rabinovich, Jan Arne Telle, Martin Vatshelle

Publication date 10 December 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-03898-8_26

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Optimal bounds on the approximation of Boolean functions with consequences on the concept of hardness
• Lower bounds for Boolean circuits of bounded negation width
• Practical algorithms for linear Boolean-width
• Optimal bounds for the approximation of Boolean functions and some applications
• Lower bounds for the complexity of restrictions of Boolean functions
• Upper bounds on the multiplicative complexity of symmetric Boolean functions
• scientific article; zbMATH DE number 806753
• On estimates on the complexity of restrictions of Boolean functions
• Bounds on an exponential sum arising in Boolean circuit complexity
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic

Cited in

(9)

• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Graph classes with structured neighborhoods and algorithmic applications
• Boolean-width of graphs
• On the Boolean-width of a graph: structure and applications
• Practical algorithms for linear Boolean-width
• Hardness of computing width parameters based on branch decompositions over the vertex set
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• Trans-dichotomous algorithms without multiplication — some upper and lower bounds
• Stability for maximal independent sets

This page was built for publication: Upper Bounds on Boolean-Width with Applications to Exact Algorithms

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