On computational complexity of graph inference from counting

DOI10.1007/s11047-012-9349-2zbMath1333.68141OpenAlexW2079011386MaRDI QIDQ269786

Yasushi Okuno, Shinnosuke Seki, Kei Taneishi, Szilárd Zsolt Fazekas, Hiro Ito

Publication date: 6 April 2016

Published in: Natural Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11047-012-9349-2

zbMATH Keywords

computational complexityspectrumcountingtree-decompositionde novo drug designgraph inferencewalk history

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Related Items

One-reversal counter machines and multihead automata: revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Absoluteness of subword inequality is undecidable
• A detachment algorithm for inferring a graph from path frequency
• A partial k-arboretum of graphs with bounded treewidth
• Subword histories and Parikh matrices
• Connected Treewidth and Connected Graph Searching
• Graph minors. II. Algorithmic aspects of tree-width
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• On Context-Free Languages
• Combinatorial Pattern Matching