Publications related to 'NP complete' : An NP-complete problem is in the complexity class NP and every problem in NP is reducible in polynomial time to this problem (Wikipedia).
 
Order by:   Type | Year
           related to:
Associated keywords
2020
1
photo
Jonathan Klawitter and Peter Stumpf. Drawing Tree-Based Phylogenetic Networks with Minimum Number of Crossings. 2020.
Keywords: explicit network, FPT, minimum number, NP complete, phylogenetic network, phylogeny, polynomial, visualization.
Note: https://arxiv.org/abs/2008.08960.
       

2019
2
photophotophotophoto
Steven Kelk, Fabio Pardi, Celine Scornavacca and Leo van Iersel. Finding the most parsimonious or likely tree in a network with respect to an alignment. In JOMB, Vol. 78:527-547, 2019.
Keywords: APX hard, from network, from sequences, likelihood, NP complete, parsimony.
Note: https://arxiv.org/abs/1707.03648.
       

3
photophotophotophoto
Janosch Döcker, Leo van Iersel, Steven Kelk and Simone Linz. Deciding the existence of a cherry-picking sequence is hard on two trees. In DAM, Vol. 260:131-143, 2019.
Keywords: cherry-picking, explicit network, hybridization, minimum number, NP complete, phylogenetic network, phylogeny, reconstruction, temporal-hybridization number, time consistent network, tree-child network.
Note: https://arxiv.org/abs/1712.02965.
       

2018
4
photophotophotophoto
Leo van Iersel, Steven Kelk, Giorgios Stamoulis, Leen Stougie and Olivier Boes. On unrooted and root-uncertain variants of several well-known phylogenetic network problems. In ALG, Vol. 80(11):2993-3022, 2018.
Keywords: explicit network, FPT, from network, from unrooted trees, NP complete, phylogenetic network, phylogeny, reconstruction, tree containment.
Note: https://hal.inria.fr/hal-01599716.
       

5
photophotophoto
Andrew R. Francis, Katharina Huber and Vincent Moulton. Tree-based unrooted phylogenetic networks. In BMB, Vol. 80(2):404-416, 2018.
Keywords: characterization, explicit network, NP complete, phylogenetic network, phylogeny, tree containment, tree-based network, unrooted tree-based network.
Note: https://arxiv.org/abs/1704.02062.
       

6
photophoto
Janosch Döcker and Simone Linz. On the existence of a cherry-picking sequence. In TCS, Vol. 714:36-50, 2018.
Keywords: cherry-picking, explicit network, from rooted trees, NP complete, phylogenetic network, phylogeny, reconstruction, temporal-hybridization number, time consistent network, tree-child network.
Note: https://arxiv.org/abs/1712.04127.
       

7
photophotophoto
Leo van Iersel, Mark Jones and Celine Scornavacca. Improved maximum parsimony models for phylogenetic networks. In SB, Vol. 67(3):518-542, 2018.
Keywords: explicit network, FPT, from sequences, NP complete, parsimony, phylogenetic network, phylogeny, reconstruction, weakly displaying.
Note: https://leovaniersel.files.wordpress.com/2017/12/improved_parsimony_networks.pdf.
       

2017
8
photophotophotophotophoto
Katharina Huber, Leo van Iersel, Vincent Moulton, Celine Scornavacca and Taoyang Wu. Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets. In ALG, Vol. 77(1):173-200, 2017.
Keywords: explicit network, FPT, from binets, from subnetworks, from trinets, NP complete, phylogenetic network, phylogeny, polynomial, reconstruction.
Note: http://arxiv.org/abs/1411.6804.
       

9
photophoto
Misagh Kordi and Mukul S. Bansal. On the Complexity of Duplication-Transfer-Loss Reconciliation with Non-Binary Gene Trees. In TCBB, Vol. 14(3):587-599, 2017.
Keywords: duplication, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction.
Note: http://compbio.engr.uconn.edu/papers/Kordi_DTLreconciliationPreprint2015.pdf.
       

10
photophotophoto
Leo van Iersel, Vincent Moulton, Eveline De Swart and Taoyang Wu. Binets: fundamental building blocks for phylogenetic networks. In BMB, Vol. 79(5):1135-1154, 2017.
Keywords: approximation, explicit network, from binets, from subnetworks, galled tree, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, reconstruction.
Note: http://dx.doi.org/10.1007/s11538-017-0275-4.
       

2016
11
photophotophotophoto
Katharina Huber, Vincent Moulton, Mike Steel and Taoyang Wu. Folding and unfolding phylogenetic trees and networks. In JOMB, Vol. 73(6):1761-1780, 2016.
Keywords: compressed network, explicit network, FU-stable network, NP complete, phylogenetic network, phylogeny, tree containment, tree sibling network.
Note: http://arxiv.org/abs/1506.04438.
       

12
photo
Maria Anaya, Olga Anipchenko-Ulaj, Aisha Ashfaq, Joyce Chiu, Mahedi Kaiser, Max Shoji Ohsawa, Megan Owen, Ella Pavlechko, Katherine St. John, Shivam Suleria, Keith Thompson and Corrine Yap. On Determining if Tree-based Networks Contain Fixed Trees. In BMB, Vol. 78(5):961-969, 2016.
Keywords: explicit network, FPT, NP complete, phylogenetic network, phylogeny, tree-based network.
Note: http://arxiv.org/abs/1602.02739.
       

13
photophotophotophotophoto
Philippe Gambette, Leo van Iersel, Steven Kelk, Fabio Pardi and Celine Scornavacca. Do branch lengths help to locate a tree in a phylogenetic network? In BMB, Vol. 78(9):1773-1795, 2016.
Keywords: branch length, explicit network, FPT, from network, from rooted trees, NP complete, phylogenetic network, phylogeny, pseudo-polynomial, time consistent network, tree containment, tree sibling network.
Note: http://arxiv.org/abs/1607.06285.
       

14
photophoto
Ioannis G. Tollis and Konstantinos G. Kakoulis. Algorithms for Visualizing Phylogenetic Networks. In GD16, Vol. 9801:183-195 of LNCS, springer, 2016.
Keywords: explicit network, galled network, galled tree, NP complete, planar, visualization.
Note: http://arxiv.org/abs/1609.00755.
       

2015
15
photophotophotophoto
Mareike Fischer, Leo van Iersel, Steven Kelk and Celine Scornavacca. On Computing The Maximum Parsimony Score Of A Phylogenetic Network. In SIDMA, Vol. 29(1):559-585, 2015.
Keywords: APX hard, cluster containment, explicit network, FPT, from network, from sequences, integer linear programming, level k phylogenetic network, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, Program MPNet, reconstruction, software.
Note: http://arxiv.org/abs/1302.2430.
       

16
photophoto
Misagh Kordi and Mukul S. Bansal. On the Complexity of Duplication-Transfer-Loss Reconciliation with Non-Binary Gene Trees. In ISBRA15, Vol. 9096:187-198 of LNCS, springer, 2015.
Keywords: duplication, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction.
Note: http://compbio.engr.uconn.edu/papers/Kordi_ISBRA2015.pdf.
       

2014
17
photophoto
Anthony Labarre and Sicco Verwer. Merging partially labelled trees: hardness and a declarative programming solution. In TCBB, Vol. 11(2):389-397, 2014.
Keywords: abstract network, from unrooted trees, heuristic, NP complete, phylogenetic network, phylogeny, reconstruction.
Note: https://hal-upec-upem.archives-ouvertes.fr/hal-00855669.
       
Toggle abstract
2013
18
photophotophoto
Peter J. Humphries, Simone Linz and Charles Semple. On the complexity of computing the temporal hybridization number for two phylogenies. In DAM, Vol. 161:871-880, 2013.
Keywords: agreement forest, APX hard, characterization, from rooted trees, hybridization, NP complete, phylogenetic network, phylogeny, reconstruction, time consistent network.
Note: http://ab.inf.uni-tuebingen.de/people/linz/publications/TAFapx.pdf.
       
Toggle abstract
19
photophotophoto
Peter J. Humphries, Simone Linz and Charles Semple. Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies. In BMB, Vol. 75(10):1879-1890, 2013.
Keywords: characterization, cherry-picking, from rooted trees, hybridization, NP complete, phylogenetic network, phylogeny, reconstruction, time consistent network.
Note: http://ab.inf.uni-tuebingen.de/people/linz/publications/CPSpaper.pdf.
       
Toggle abstract
2011
20
photophotophoto
Ali Tofigh, Mike Hallett and Jens Lagergren. Simultaneous Identification of Duplications and Lateral Gene Transfers. In TCBB, Vol. 8(2):517-535, 2011.
Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction.
Note: http://dx.doi.org/10.1109/TCBB.2010.14.
       
Toggle abstract
21
photophoto
Leo van Iersel and Steven Kelk. When two trees go to war. In JTB, Vol. 269(1):245-255, 2011.
Keywords: APX hard, explicit network, from clusters, from rooted trees, from sequences, from triplets, level k phylogenetic network, minimum number, NP complete, phylogenetic network, phylogeny, polynomial, reconstruction.
Note: http://arxiv.org/abs/1004.5332.
       
Toggle abstract
2010
22
photophotophoto
Simone Linz, Charles Semple and Tanja Stadler. Analyzing and reconstructing reticulation networks under timing constraints. In JOMB, Vol. 61(5):715-737, 2010.
Keywords: explicit network, from rooted trees, hybridization, lateral gene transfer, NP complete, phylogenetic network, phylogeny, reconstruction, time consistent network.
Note: http://dx.doi.org/10.1007/s00285-009-0319-y..
       
Toggle abstract
23
photophotophoto
Leo van Iersel, Charles Semple and Mike Steel. Locating a tree in a phylogenetic network. In IPL, Vol. 110(23), 2010.
Keywords: cluster containment, explicit network, from network, level k phylogenetic network, normal network, NP complete, phylogenetic network, polynomial, regular network, time consistent network, tree containment, tree sibling network, tree-child network.
Note: http://arxiv.org/abs/1006.3122.
       
Toggle abstract
24
photo
Philippe Gambette. Méthodes combinatoires de reconstruction de réseaux phylogénétiques. PhD thesis, Université Montpellier 2, France, 2010.
Keywords: abstract network, characterization, circular split system, explicit network, FPT, from clusters, from triplets, integer linear programming, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, Program Dendroscope, pyramid, reconstruction, split network, weak hierarchy.
Note: http://tel.archives-ouvertes.fr/tel-00608342/en/.
       

2009
25
photophotophoto
Leo van Iersel, Steven Kelk and Matthias Mnich. Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks. In JBCB, Vol. 7(4):597-623, 2009.
Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, reconstruction, uniqueness.
Note: http://arxiv.org/pdf/0712.2932v2.
       

26
photophoto
Ran Libeskind-Hadas and Michael A. Charleston. On the Computational Complexity of the Reticulate Cophylogeny Reconstruction Problem. In JCB, Vol. 16(1):105-117, 2009.
Keywords: cophylogeny, heuristic, NP complete, parsimony, phylogenetic network, reconstruction.
Note: http://dx.doi.org/10.1089/cmb.2008.0084.
       
Toggle abstract
27
photophotophotophotophoto
Daniel H. Huson, Regula Rupp, Vincent Berry, Philippe Gambette and Christophe Paul. Computing Galled Networks from Real Data. In ISMBECCB09, Vol. 25(12):i85-i93 of BIO, 2009.
Keywords: abstract network, cluster containment, explicit network, FPT, from clusters, from rooted trees, galled network, NP complete, phylogenetic network, phylogeny, polynomial, Program Dendroscope, reconstruction.
Note: http://hal-lirmm.ccsd.cnrs.fr/lirmm-00368545/en/.
       
Toggle abstract
28
photo
Ali Tofigh. Using Trees to Capture Reticulate Evolution, Lateral Gene Transfers and Cancer Progression. PhD thesis, KTH Royal Institute of Technology, Sweden, 2009.
Keywords: duplication, dynamic programming, from multilabeled tree, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction.
Note: http://kth.diva-portal.org/smash/record.jsf?pid=diva2:220830&searchId=1.
       

2008
29
photophotophotophotophotophoto
Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, Ferry Hagen and Teun Boekhout. Constructing level-2 phylogenetic networks from triplets. In RECOMB08, Vol. 4955:450-462 of LNCS, springer, 2008.
Keywords: explicit network, from triplets, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, polynomial, Program Level2, reconstruction.
Note: http://homepages.cwi.nl/~iersel/level2full.pdf. An appendix with proofs can be found here http://arxiv.org/abs/0707.2890.
       
Toggle abstract
30
photophotophotophoto
Iyad A. Kanj, Luay Nakhleh, Cuong Than and Ge Xia. Seeing the Trees and Their Branches in the Network is Hard. In TCS, Vol. 401:153-164, 2008.
Keywords: evaluation, from network, from rooted trees, NP complete, phylogenetic network, phylogeny, tree containment.
Note: http://www.cs.rice.edu/~nakhleh/Papers/tcs08.pdf.
       

2007
31
photophoto
Magnus Bordewich and Charles Semple. Computing the minimum number of hybridization events for a consistent evolutionary history. In DAM, Vol. 155:914-918, 2007.
Keywords: agreement forest, approximation, APX hard, explicit network, from rooted trees, hybridization, inapproximability, NP complete, phylogenetic network, phylogeny, SPR distance.
Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS06a.pdf.
       

32
photophotophotophoto
Iyad A. Kanj, Luay Nakhleh, Cuong Than and Ge Xia. Seeing the Trees and Their Branches in the Network is Hard. In Proceedings of the Tenth Italian Conference on Theoretical Computer Science (ICTCS'07), 2007.
Keywords: evaluation, from network, from rooted trees, NP complete, phylogenetic network, phylogeny, tree containment.
Note: http://www.cs.rice.edu/~nakhleh/Papers/ictcs07.pdf.
       

33
photophotophotophoto
Cam Thach Nguyen, Nguyen Bao Nguyen, Wing-Kin Sung and Louxin Zhang. Reconstructing Recombination Network from Sequence Data: The Small Parsimony Problem. In TCBB, Vol. 4(3):394-402, 2007.
Keywords: explicit network, from sequences, labeling, NP complete, parsimony, phylogenetic network, phylogeny.
Note: http://www.cs.washington.edu/homes/ncthach/Papers/TCBB2007.pdf.
       

2006
34
photo
Pawel Górecki. Detection of horizontal gene transfer. PhD thesis, Warsaw University, Poland, 2006.
Keywords: explicit network, from rooted trees, from species tree, lateral gene transfer, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction.
       

2005
35
photophoto
Magnus Bordewich and Charles Semple. On the computational complexity of the rooted subtree prune and regraft distance. In ACOM, Vol. 8:409-423, 2005.
Keywords: agreement forest, from rooted trees, NP complete, SPR distance.
Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS04.pdf.
       
Toggle abstract
36
photophotophotophoto
Charles Choy, Jesper Jansson, Kunihiko Sadakane and Wing-Kin Sung. Computing the maximum agreement of phylogenetic networks. In TCS, Vol. 335(1):93-107, 2005.
Keywords: dynamic programming, FPT, level k phylogenetic network, MASN, NP complete, phylogenetic network, phylogeny.
Note: http://www.df.lth.se/~jj/Publications/masn8_TCS2005.pdf.
       
Toggle abstract
37
photophotophotophoto
Trinh N. D. Huynh, Jesper Jansson, Nguyen Bao Nguyen and Wing-Kin Sung. Constructing a Smallest Refining Galled Phylogenetic Network. In RECOMB05, Vol. 3500:265-280 of LNCS, springer, 2005.
Keywords: from rooted trees, galled tree, NP complete, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction.
Note: http://www.df.lth.se/~jj/Publications/refining_gn3_RECOMB2005.pdf.
       

38
photophoto
Jesper Jansson and Wing-Kin Sung. The Maximum Agreement of Two Nested Phylogenetic Networks. In ISAAC04, Vol. 3341:581-593 of LNCS, springer, 2005.
Keywords: dynamic programming, MASN, nested network, NP complete, phylogenetic network, phylogeny, polynomial.
Note: http://www.df.lth.se/~jj/Publications/nested7_ISAAC2004.pdf.
       

2004
39
photophotophotophoto
Charles Choy, Jesper Jansson, Kunihiko Sadakane and Wing-Kin Sung. Computing the maximum agreement of phylogenetic networks. In Proceedings of Computing: the Tenth Australasian Theory Symposium (CATS'04), Vol. 91:134-147 of Electronic Notes in Theoretical Computer Science, 2004.
Keywords: dynamic programming, FPT, level k phylogenetic network, MASN, NP complete, phylogenetic network, phylogeny.
Note: http://www.df.lth.se/~jj/Publications/masn6_CATS2004.pdf.
       
Toggle abstract
40
photophotophoto
Mike Hallett, Jens Lagergren and Ali Tofigh. Simultaneous Identification of Duplications and Lateral Transfers. In RECOMB04, Pages 347-356, 2004.
Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction.
Note: http://www.nada.kth.se/~jensl/p164-hallett.pdf.
       

41
photophoto
Mike Hallett and Jens Lagergren. Efficient algorithms for lateral gene transfers problems. 2004.
Keywords: from rooted trees, lateral gene transfer, NP complete, phylogeny, polynomial, reconstruction.
Note: submitted to SIAM Journal on Computing, http://www.mcb.mcgill.ca/~hallett/Lateral.pdf.
       

42
photo
Pawel Górecki. Reconciliation problems for duplication, loss and horizontal gene transfer. In RECOMB04, Pages 316-325, 2004.
Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction.
Note: http://ai.stanford.edu/~serafim/CS374_2004/Papers/Gorecki_Reconciliation.pdf.
       

2003
43
photo
Pawel Górecki. Single step reconciliation algorithm for duplication, loss and horizontal gene transfer model. In ECCB03, 2003.
Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction.
Note: http://www.inra.fr/eccb2003/posters/pdf/short/S_gorecki.ps.
       

2001
44
photophoto
Mike Hallett and Jens Lagergren. Efficient algorithms for lateral gene transfers problems. In RECOMB01, Pages 141-148, 2001.
Keywords: from rooted trees, lateral gene transfer, NP complete, phylogeny, polynomial, Program McKiTscH, reconstruction.
Note: http://dx.doi.org/10.1145/369133.369188.
       

45
photophotophoto
Lusheng Wang, Kaizhong Zhang and Louxin Zhang. Perfect phylogenetic networks with recombination. In SAC01, Pages 46-50, 2001.
Keywords: from sequences, galled tree, NP complete, perfect, phylogenetic network, phylogeny, polynomial, recombination, reconstruction.
Note: http://dx.doi.org/10.1145/372202.372271.
       

1998
46
photophoto
John Kececioglu and Dan Gusfield. Reconstructing a history of recombinations from a set of sequences. In DAM, Pages 239-260, 1998.
Keywords: from sequences, NP complete, polynomial, recombination, reconstruction.
Note: http://citeseer.ist.psu.edu/76600.html.
       

1994
47
photophoto
John Kececioglu and Dan Gusfield. Reconstructing a history of recombinations from a set of sequences. In SODA94, Pages 471-480, 1994.
Keywords: from sequences, NP complete, polynomial, recombination, reconstruction.
Note: http://portal.acm.org/citation.cfm?id=314626#.
       

1986
48
photo
Ingo Althöfer. On optimal realizations of finite metric spaces by graphs. In Discrete and Computational Geometry, Vol. 3(1):103-122, 1986.
Keywords: NP complete, optimal realization, realization.
Note: http://dx.doi.org/10.1007/BF02187901.
       
Toggle abstract