Complexity of splits reconstruction for low-degree trees

DOI10.1016/j.dam.2014.08.005zbMath1303.05028OpenAlexW4205985989WikidataQ62046030 ScholiaQ62046030MaRDI QIDQ476307

Serge Gaspers, Karol Suchan, Mathieu Liedloff, Maya Jakobine Stein

Publication date: 28 November 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.08.005

zbMATH Keywords

computational complexitycomputational chemistryreconstruction of trees

Mathematics Subject Classification ID

Trees (05C05) Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Uses Software

• OCOTILLO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
• Parameterizing by the number of numbers
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
• Special issue: 50th anniversary of the Wiener index
• Parametrized complexity theory.
• A class of trees and its Wiener index
• All but 49 numbers are Wiener indices of trees
• Complexity of Splits Reconstruction for Low-Degree Trees
• Multivariate Complexity Theory
• A 6-Approximation Algorithm for Computing Smallest Common AoN-Supertree with Application to the Reconstruction of Glycan Trees
• Wiener index of trees: Theory and applications

This page was built for publication: Complexity of splits reconstruction for low-degree trees