Complexity of modification problems for reciprocal best match graphs

DOI10.1016/j.tcs.2019.12.033zbMath1443.92120arXiv1907.08865OpenAlexW2998742065WikidataQ126398569 ScholiaQ126398569MaRDI QIDQ2290642

Manuela Geiß, Marc Hellmuth, Peter F. Stadler

Publication date: 29 January 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1907.08865

zbMATH Keywords

NP-hardnessparameterized algorithmseditingorthology relationbicluster graphhierarchically colored cographsreciprocal best matches

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10) Computational methods for problems pertaining to biology (92-08)

Related Items (3)

Complete characterization of incorrect orthology assignments in best match graphs ⋮ Complexity of modification problems for best match graphs ⋮ Indirect identification of horizontal gene transfer

Cites Work

• Improved biclustering of microarray data demonstrated through systematic performance tests
• Exact algorithms for cluster editing: Evaluation and experiments
• Complexity and parameterized algorithms for cograph editing
• Some perfect coloring properties of graphs
• Complement reducible graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• The maximum edge biclique problem is NP-complete
• New heuristics for the bicluster editing problem
• Orthology relations, symbolic ultrametrics, and cographs
• Applying modular decomposition to parameterized cluster editing problems
• Best match graphs
• Biclustering in data mining
• On Bipartite and Multipartite Clique Problems
• Hybrid Metaheuristic for Bicluster Editing Problem
• Biclustering via Sparse Singular Value Decomposition
• Improved Algorithms for Bicluster Editing
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Approximating Clique and Biclique Problems
• Biclustering with heterogeneous variance
• Fast biclustering by dual parameterization
• Correlation Clustering and Biclustering With Locally Bounded Errors

This page was built for publication: Complexity of modification problems for reciprocal best match graphs