Solving a special case of the P conjecture using dependency graphs with dissolution

DOI10.1007/978-3-319-73359-3_13MaRDI QIDQ1749169zbMATH OpenOpenAlexFDO

Authors Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron

Publication date 16 May 2018

Full work available at URL https://doi.org/10.1007/978-3-319-73359-3_13

Mathematics Subject Classification ID

Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Recommendations

• The complexity of dissociation set problems in graphs
• Solvability of theories of certain classes of elimination graphs
• Almost resolvable P_k‐decompositions of complete graphs
• Solving the \(k\)-independent sets problem of graphs by Gröbner bases
• Polynomial cases of graph decomposition: A complete solution of Holyer's problem
• Conditional resolvability in graphs: a survey
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• Complexity, Graphs, and the Dependency Pair Method
• Towards Gallai's path decomposition conjecture
• Solving problems on special classes of graphs

Cited in

(7)

• A characterisation of \textbf{P} by \textbf{DLOGTIME}-uniform families of polarizationless P systems using only dissolution rules
• P systems attacking hard problems beyond NP: a survey
• Seeking computational efficiency boundaries: the Păun's conjecture
• A new method to simulate restricted variants of polarizationless P systems with active membranes
• On a partial affirmative answer for a Păun's conjecture
• On the power of P systems with active membranes using weak non-elementary membrane division
• On the power of membrane dissolution in polarizationless P systems with active membranes

This page was built for publication: Solving a special case of the P conjecture using dependency graphs with dissolution

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