Barnette's conjecture through the lens of the \(Mod_k P\) complexity classes

DOI10.1007/978-3-030-90048-9_6OpenAlexW3209751793MaRDI QIDQ2695474

Robert D. Barish, Akira Suyama

Publication date: 31 March 2023

Full work available at URL: https://doi.org/10.1007/978-3-030-90048-9_6

Mathematics Subject Classification ID

Applications of game theory (91A80) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Inductive definition of two restricted classes of triangulations
• Relations among MOD-classes
• Edge reductions in cyclically \(k\)-connected cubic graphs
• A note on 3-connected cubic planar graphs
• On the construction of parallel computers from various basis of Boolean functions
• NP is as easy as detecting unique solutions
• Counting linear extensions
• The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
• PRIMES is in P
• Construction of Barnette graphs whose large subgraphs are non-Hamiltonian
• The Complexity of Enumeration and Reliability Problems
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Reducibility among Combinatorial Problems
• Polytopes, graphs, and complexes
• The complexity of theorem-proving procedures
• Computing and Combinatorics
• On Hamiltonian Circuits
• Counting classes: Thresholds, parity, mods, and fewness

This page was built for publication: Barnette's conjecture through the lens of the \(Mod_k P\) complexity classes