Image de couverture de livre

Recognizing Level-k-Based Phylogenetic Networks is NP-Complete

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Suzuki, Takatora
Format:	Preprint
Publié:	2026
Sujets:	Populations and Evolution Discrete Mathematics 05C20 (Primary), 05C85, 68Q17, 92D15 (Secondary)
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Which Phylogenetic Networks are Level-k Networks with Additional Arcs? Structure and Algorithms
par: Suzuki, Takatora, et autres
Publié: (2025)

Perfect phylogenies via the Minimum Uncovering Branching problem: efficiently solvable cases
par: Baghirova, Narmina, et autres
Publié: (2025)

Reconfiguring homomorphisms to reflexive graphs via a simple reduction
par: Mühlenthaler, Moritz, et autres
Publié: (2024)

Edge open packing: complexity, algorithmic aspects, and bounds
par: Brešar, Boštjan, et autres
Publié: (2024)

Phylogenetic diversity indices from an affine and projective viewpoint
par: Moulton, Vincent, et autres
Publié: (2024)

Transformations to simplify phylogenetic networks
par: Heiss, Johanna, et autres
Publié: (2024)

A lattice structure for ancestral configurations arising from the relationship between gene trees and species trees
par: Lappo, Egor, et autres
Publié: (2021)

On the joint embedding property for cographs and trees
par: Carter, Daniel
Publié: (2024)

Characterizations of undirected 2-quasi best match graphs
par: Korchmaros, Annachiara, et autres
Publié: (2025)

The $B_2$ index of galled trees
par: Bienvenu, François, et autres
Publié: (2024)

Pathographs and some (un)decidability results
par: Carter, Daniel, et autres
Publié: (2025)

Size and shape of terrestrial animals
par: Sharma, Neelima, et autres
Publié: (2026)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
par: Abdullah, Duaa, et autres
Publié: (2025)

Complexity of Sequence-to-Graph Alignment with Co-Linear Chaining
par: Li, Xingfu
Publié: (2026)

Finding cliques and dense subgraphs using edge queries
par: Csóka, Endre, et autres
Publié: (2023)

Mathematically tractable models of random phylogenetic networks: an overview of some recent developments
par: Bienvenu, François
Publié: (2024)

Arboreal networks and their underlying trees
par: Huber, Katharina T., et autres
Publié: (2025)

Vector encoding of phylogenetic trees by ordered leaf attachment
par: Richman, Harry, et autres
Publié: (2025)

Homomorphically Full Oriented Graphs
par: Bellitto, Thomas, et autres
Publié: (2022)

Pattern formation within phenotype-structured chemotactic populations
par: Lorenzi, Tommaso, et autres
Publié: (2025)

On a phenotype-structured Shigesada--Kawasaki--Teramoto model: Turing instability and pattern selection under fast phenotype switching
par: Cusseddu, Davide, et autres
Publié: (2026)

An NP-hardness result for the colored constrained maximum 2-edge-colorable subgraph problem in bipartite graphs
par: Mkrtchyan, Vahan
Publié: (2024)

Linear extensions of finite posets
par: Chan, Swee Hong, et autres
Publié: (2023)

A greedy heuristic for graph burning
par: García-Díaz, Jesús, et autres
Publié: (2024)

A dichotomy law for certain classes of phylogenetic networks
par: Fuchs, Michael, et autres
Publié: (2025)

Phylogenetic invariants: straightforward from the general Markov to equivariant models
par: Casanellas, Marta, et autres
Publié: (2023)

More algorithmic results for problems of spread of influence in edge-weighted graphs with and without incentives
par: Askari, Siavash, et autres
Publié: (2024)

Combinatorial properties of continuous graphs: A survey of challenges, solutions and open problems
par: Grigoriev, Alexander, et autres
Publié: (2025)

Conformal Hypergraphs: Duality and Implications for the Upper Clique Transversal Problem
par: Boros, Endre, et autres
Publié: (2023)

Conformality of Minimal Transversals of Maximal Cliques
par: Boros, Endre, et autres
Publié: (2024)

Results on three problems on isolation of graphs
par: Borg, Peter, et autres
Publié: (2026)

4-cop-win graphs have at least 19 vertices
par: Turcotte, Jérémie, et autres
Publié: (2020)

Polynomial-Time Solutions for Longest Common Subsequence Related Problems Between a Sequence and a Pangenome Graph
par: Li, Xingfu, et autres
Publié: (2026)

Labeled histories and maximally probable labeled topologies with multifurcation
par: Dickey, Emily H., et autres
Publié: (2025)

Computation of Minimum Numbers of Tile and Bond-Edge Types for DNA Self-Assembly of Select Archimedean Graphs
par: Merrithew, Tabitha, et autres
Publié: (2025)

The Upper Clique Transversal Problem
par: Milanič, Martin, et autres
Publié: (2023)

Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
par: Furmańczyk, Hanna, et autres
Publié: (2020)

Computational complexity of counting coincidences
par: Chan, Swee Hong, et autres
Publié: (2023)

Structure and algorithms for graphs excluding grids with small parity breaks as odd-minors
par: Gollin, J. Pascal, et autres
Publié: (2023)

Predicting the depth of the most recent common ancestor of a random sample of $k$ species: the impact of phylogenetic tree shape
par: Fuchs, Michael, et autres
Publié: (2025)