Image de couverture de livre

Width Hierarchy for k-OBDD of Small Width

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Khadiev, Kamil
Format:	Preprint
Publié:	2015
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

On the Hierarchies for Deterministic, Nondeterministic and Probabilistic Ordered Read-k-times Branching Programs
par: Khadiev, Kamil
Publié: (2016)

Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
par: Khadiev, Kamil, et autres
Publié: (2017)

Efficient Algorithms for Quantum Hashing
par: Zinnatullin, Ilnar, et autres
Publié: (2025)

Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language
par: Khadiev, Kamil, et autres
Publié: (2024)

Bisection Width, Discrepancy, and Eigenvalues of Hypergraphs
par: Räty, Eero, et autres
Publié: (2024)

FPT Parameterisations of Fractional and Generalised Hypertree Width
par: Lanzinger, Matthias, et autres
Publié: (2025)

Fast Matrix Multiplication meets the Submodular Width
par: Abo-Khamis, Mahmoud, et autres
Publié: (2024)

Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
par: Khamis, Mahmoud Abo, et autres
Publié: (2026)

Clique-Width: Harnessing the Power of Atoms
par: Dabrowski, Konrad K., et autres
Publié: (2020)

Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism
par: Berkholz, Christoph, et autres
Publié: (2024)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
par: Baril, Ambroise, et autres
Publié: (2025)

Solving Problems on Generalized Convex Graphs via Mim-Width
par: Bonomo-Braberman, Flavia, et autres
Publié: (2020)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths
par: Beisegel, Jesse, et autres
Publié: (2025)

Mim-Width is paraNP-complete
par: Bergougnoux, Benjamin, et autres
Publié: (2025)

The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
par: Beisegel, Jesse, et autres
Publié: (2024)

Coloring Hardness on Low Twin-Width Graphs
par: Bonnet, Édouard
Publié: (2025)

Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions
par: Podolskii, Vladimir, et autres
Publié: (2024)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers
par: Beisegel, Jesse, et autres
Publié: (2025)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
par: Beisegel, Jesse, et autres
Publié: (2025)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
par: Bergougnoux, Benjamin, et autres
Publié: (2025)

A Hierarchy for Constant Communication Complexity
par: Ambainis, Andris, et autres
Publié: (2025)

Hierarchies within TFNP: building blocks and collapses
par: Ghentiyala, Surendra, et autres
Publié: (2025)

Hilbert's Nullstellensatz is in the Counting Hierarchy
par: Andrews, Robert, et autres
Publié: (2026)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
par: Bhattacharjee, Sutanay, et autres
Publié: (2026)

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
par: Gajulapalli, Karthik, et autres
Publié: (2025)

On a Hierarchy of Spectral Invariants for Graphs
par: Arvind, V., et autres
Publié: (2023)

Small unsatisfiable $k$-CNFs with bounded literal occurrence
par: Zhang, Tianwei, et autres
Publié: (2024)

The Entangled Quantum Polynomial Hierarchy Collapses
par: Grewal, Sabee, et autres
Publié: (2024)

A SUBSET-SUM Characterisation of the A-Hierarchy
par: Gutleben, Jan, et autres
Publié: (2024)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
par: Agarwal, Avantika, et autres
Publié: (2024)

Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy
par: Ganian, Robert, et autres
Publié: (2025)

Hausdorff Reductions and the Exponential Hierarchies
par: Malizia, Enrico
Publié: (2024)

On Approximability of Satisfiable k-CSPs: V
par: Bhangale, Amey, et autres
Publié: (2024)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
par: Grüne, Christoph, et autres
Publié: (2026)

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
par: Grewal, Sabee, et autres
Publié: (2025)

Good Locally Testable Codes with Small Alphabet and Small Query Size
par: First, Uriya, et autres
Publié: (2025)

Near Optimal Hardness of Approximating $k$-CSP
par: Minzer, Dor, et autres
Publié: (2025)

Trading Determinism for Time: The k-Reach Problem
par: Bhadra, Ronak, et autres
Publié: (2024)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
par: S., Karthik C., et autres
Publié: (2021)

On Extremal Properties of k-CNF: Capturing Threshold Functions
par: Gurumukhani, Mohit, et autres
Publié: (2024)