Upper Bounds on Boolean-Width with Applications to Exact Algorithms
From MaRDI portal
Publication:2867092
DOI10.1007/978-3-319-03898-8_26zbMATH Open1407.68370OpenAlexW404522508MaRDI QIDQ2867092FDOQ2867092
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)
Cited In (9)
- 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
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
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)
