Search results for "superstring"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
98	Jin Wook Kim, Siwon Choi, Joong Chae Na, Jeong Seop Sim	Improved Algorithms for Finding Consistent Superstrings Based on a New Graph Model.	ISAAC	2009	DBLP DOI BibTeX RDF	consistent superstring, Aho-Corasick algorithm, string inclusion, string non-inclusion
98	Avrim Blum, Tao Jiang 0001, Ming Li 0001, John Tromp, Mihalis Yannakakis	Linear Approximation of Shortest Superstrings.	J. ACM	1994	DBLP DOI BibTeX RDF	shortest common superstring, approximation algorithm
79	Lucian Ilie, Liviu Tinta, Cristian Popescu, Kathleen A. Hill	Viral Genome Compression.	DNA	2006	DBLP DOI BibTeX RDF	viral genomes, genome compression, overlapping genes, shortest common superstring problem, lower bounds, exact algorithms, viruses, approximate solutions
79	Maik Weinard, Georg Schnitger	On the Greedy Superstring Conjecture.	FSTTCS	2003	DBLP DOI BibTeX RDF
79	Serafim Batzoglou, Sorin Istrail	Physical Mapping with Repeated Probes: The Hypergraph Superstring Problem.	CPM	1999	DBLP DOI BibTeX RDF
67	Zhengjun Cao, Lihua Liu, Olivier Markowitch	Generalized Greedy Algorithm for Shortest Superstring.	Complex (2)	2009	DBLP DOI BibTeX RDF	shortest superstring, optimal set, greedy algorithm
67	Lucas Ledesma, Daniel Manrique, Alfonso Rodríguez-Patón	A tissue P system and a DNA microfluidic device for solving the shortest common superstring problem.	Soft Comput.	2005	DBLP DOI BibTeX RDF	Microflow reactor, Shortest common superstring problem, DNA computing, Membrane computing
60	Virginia Vassilevska	Explicit Inapproximability Bounds for the Shortest Superstring Problem.	MFCS	2005	DBLP DOI BibTeX RDF
60	Heidi J. Romero, Carlos A. Brizuela, Andrei Tchernykh	An Experimental Comparison of Approximation Algorithms for the Shortest Common Superstring Problem.	ENC	2004	DBLP DOI BibTeX RDF
60	Alan M. Frieze, Wojciech Szpankowski	Greedy Algorithms for the Shortest Common Superstring that are Asmtotically Optimal.	ESA	1996	DBLP DOI BibTeX RDF
55	Artur Czumaj, Leszek Gasieniec, Marek Piotrów, Wojciech Rytter	Parallel and Sequential Approximations of Shortest Superstrings.	SWAT	1994	DBLP DOI BibTeX RDF
50	Shang-Hua Teng, F. Frances Yao	Approximating Shortest Superstrings	FOCS	1993	DBLP DOI BibTeX RDF	superstring, shortest superstrings, Shortest Superstring Problem, approximation algorithms, data compression, NP-hard, DNA sequencing, MAX SNP-hard
50	Ming Li 0001	Towards a DNA Sequencing Theory (Learning a String) (Preliminary Version)	FOCS	1990	DBLP DOI BibTeX RDF	shortest common superstring, superstring learning, randomly drawn substrings, samples, efficient algorithm, DNA sequencing
48	Bastien Cazaux, Eric Rivals	Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring.	CoRR	2020	DBLP BibTeX RDF
42	Davide Bilò, Hans-Joachim Böckenhauer, Dennis Komm, Richard Královic, Tobias Mömke, Sebastian Seibert, Anna Zych	Reoptimization of the Shortest Common Superstring Problem.	CPM	2009	DBLP DOI BibTeX RDF
42	Kai Plociennik	A Probabilistic PTAS for Shortest Common Superstring.	MFCS	2009	DBLP DOI BibTeX RDF
42	Bin Ma 0002	Why Greed Works for Shortest Common Superstring Problem.	CPM	2008	DBLP DOI BibTeX RDF
42	Luis C. González, Heidi J. Romero, Carlos A. Brizuela	A Genetic Algorithm for the Shortest Common Superstring Problem.	GECCO (2)	2004	DBLP DOI BibTeX RDF
42	Luis Carlos González-Gurrola, Carlos A. Brizuela, Everardo Gutiérrez	A Genetic Algorithm for the Shortest Common Superstring Problem.	IBERAMIA	2004	DBLP DOI BibTeX RDF
36	Fang-Xiang Wu, Wen-Jun Zhang 0001, Anthony J. Kusalik	An Algorithm to Reconstruct a Target DNA Sequence from Its Spectrum Connected at a Given Level.	BIBE	2003	DBLP DOI BibTeX RDF
36	Jorma Tarhio, Esko Ukkonen	A Greedy Algorithm for Constructing Shortest Common Superstrings.	MFCS	1986	DBLP DOI BibTeX RDF
25	Lawrence D'Antonio	Incorporating bioinformatics in an algorithms course.	ITiCSE	2003	DBLP DOI BibTeX RDF	palindromes, sequence assembly, shortest common superstring problem, dynamic programming, bioinformatics, sequence alignment
25	S. Rao Kosaraju, James K. Park, Clifford Stein 0001	Long Tours and Short Superstrings (Preliminary Version)	FOCS	1994	DBLP DOI BibTeX RDF	shortest-superstring problem, short superstrings, long tours, weight-maximizing variants, weight-minimizing counterparts, nontrivial approximation algorithms, directed graphs, traveling-salesman problems, undirected graphs, MAX SNP-hard
24	Pavel E. Kalugin, Maksim S. Nikolaev	The greedy algorithm for the Shortest Common Superstring problem is a ½-approximation in terms of compression: a simple proof.	SOSA	2024	DBLP DOI BibTeX RDF
24	Kamil Khadiev, Carlos Manuel Bosch Machado, Zeyu Chen, Junde Wu	Quantum Algorithms for the Shortest Common Superstring and Text Assembling Problems.	CoRR	2023	DBLP DOI BibTeX RDF
24	Bo Guan, Nazanin Takbiri, Dennis Goeckel, Amir Houmansadr, Hossein Pishro-Nik	Superstring-Based Sequence Obfuscation to Thwart Pattern Matching Attacks.	IEEE Internet Things J.	2022	DBLP DOI BibTeX RDF
24	Luis Antonio Fernández, Victor Martin-Mayor, David Yllanes	Phase transition in the computational complexity of the shortest common superstring and genome assembly.	CoRR	2022	DBLP DOI BibTeX RDF
24	Kamil Khadiev, Carlos Manuel Bosch Machado	Quantum Algorithm for the Shortest Superstring Problem.	CoRR	2021	DBLP BibTeX RDF
24	Maksim Nikolaev	All instantiations of the greedy algorithm for the shortest superstring problem are equivalent.	CoRR	2021	DBLP BibTeX RDF
24	Bo Guan, Nazanin Takbiri, Dennis Goeckel, Amir Houmansadr, Hossein Pishro-Nik	Superstring-Based Sequence Obfuscation to Thwart Pattern Matching Attacks.	CoRR	2021	DBLP BibTeX RDF
24	Maksim S. Nikolaev	All Instantiations of the Greedy Algorithm for the Shortest Common Superstring Problem are Equivalent.	SPIRE	2021	DBLP DOI BibTeX RDF
24	Katarzyna Paluch 0001	New Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring.	CoRR	2020	DBLP BibTeX RDF
24	Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin, Maksim Nikolaev	Collapsing Superstring Conjecture.	APPROX-RANDOM	2019	DBLP DOI BibTeX RDF
24	Tristan Braquelaire, Marie Gasparoux, Mathieu Raffinot, Raluca Uricaru	On improving the approximation ratio of the r-shortest common superstring problem.	CoRR	2018	DBLP BibTeX RDF
24	Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin	Collapsing Superstring Conjecture.	CoRR	2018	DBLP BibTeX RDF
24	Bastien Cazaux, Eric Rivals	Relationship between superstring and compression measures: New insights on the greedy conjecture.	Discret. Appl. Math.	2018	DBLP DOI BibTeX RDF
24	Bastien Cazaux, Samuel Juhel, Eric Rivals	Practical lower and upper bounds for the Shortest Linear Superstring.	SEA	2018	DBLP DOI BibTeX RDF
24	Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh 0001	Parameterized Complexity of Superstring Problems.	Algorithmica	2017	DBLP DOI BibTeX RDF
24	Jarno Alanko, Tuukka Norri	Greedy Shortest Common Superstring Approximation in Compact Space.	CoRR	2017	DBLP BibTeX RDF
24	Marcin Mucha	Shortest Superstring.	CPM	2017	DBLP DOI BibTeX RDF
24	Tristan Braquelaire, Marie Gasparoux, Mathieu Raffinot, Raluca Uricaru	On the Shortest Common Superstring of NGS Reads.	TAMC	2017	DBLP DOI BibTeX RDF
24	Jarno Alanko, Tuukka Norri	Greedy Shortest Common Superstring Approximation in Compact Space.	SPIRE	2017	DBLP DOI BibTeX RDF
24	Gabriele Fici, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen	On the greedy algorithm for the Shortest Common Superstring problem with reversals.	Inf. Process. Lett.	2016	DBLP DOI BibTeX RDF
24	Tristan Braquelaire, Marie Gasparoux, Mathieu Raffinot, Raluca Uricaru	A note on the shortest common superstring of NGS reads.	CoRR	2016	DBLP BibTeX RDF
24	Yun William Yu	Approximation hardness of Shortest Common Superstring variants.	CoRR	2016	DBLP BibTeX RDF
24	Bastien Cazaux, Gustavo Sacomoto, Eric Rivals	Superstring Graph: A New Approach for Genome Assembly.	AAIM	2016	DBLP DOI BibTeX RDF
24	Bastien Cazaux	Approximation de superchaîne, indexation et assemblage de génome. (Approximation of superstring, indexation and genome assembly).		2016	RDF
24	Paola Bonizzoni, Riccardo Dondi, Giancarlo Mauri, Italo Zoppis	Restricted and Swap Common Superstring: A Multivariate Algorithmic Perspective.	Algorithmica	2015	DBLP DOI BibTeX RDF
24	Gabriele Fici, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen	On the Greedy Algorithm for the Shortest Common Superstring Problem with Reversals.	CoRR	2015	DBLP BibTeX RDF
24	Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh 0001	Parameterized Complexity of Superstring Problems.	CoRR	2015	DBLP BibTeX RDF
24	Theodoros P. Gevezes, Leonidas S. Pitsoulis	A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem.	J. Comb. Optim.	2015	DBLP DOI BibTeX RDF
24	Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh 0001	Parameterized Complexity of Superstring Problems.	CPM	2015	DBLP DOI BibTeX RDF
24	Kai Plociennik	A probabilistic PTAS for shortest common superstring.	Theor. Comput. Sci.	2014	DBLP DOI BibTeX RDF
24	Katarzyna E. Paluch 0001	Better Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring.	CoRR	2014	DBLP BibTeX RDF
24	Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin	Approximating Shortest Superstring Problem Using de Bruijn Graphs.	CPM	2013	DBLP DOI BibTeX RDF
24	Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin	Solving 3-Superstring in 3 n/3 Time.	MFCS	2013	DBLP DOI BibTeX RDF
24	Marek Karpinski, Richard Schmied	Improved Inapproximability Results for the Shortest Superstring and Related Problems.	CATS	2013	DBLP BibTeX RDF
24	David B. Blaschke, Mariusz P. Dabrowski	Conformal Relativity versus Brans-Dicke and Superstring Theories.	Entropy	2012	DBLP DOI BibTeX RDF
24	Paola Bonizzoni, Riccardo Dondi, Giancarlo Mauri, Italo Zoppis	Restricted and Swap Common Superstring: A Parameterized View.	IPEC	2012	DBLP DOI BibTeX RDF
24	Davide Bilò, Hans-Joachim Böckenhauer, Dennis Komm, Richard Královic, Tobias Mömke, Sebastian Seibert, Anna Zych	Reoptimization of the Shortest Common Superstring Problem.	Algorithmica	2011	DBLP DOI BibTeX RDF
24	Marek Karpinski, Richard Schmied	Improved Lower Bounds for the Shortest Superstring and Related Problems.	Electron. Colloquium Comput. Complex.	2011	DBLP BibTeX RDF
24	Marek Karpinski, Richard Schmied	Improved Lower Bounds for the Shortest Superstring and Related Problems	CoRR	2011	DBLP BibTeX RDF
24	Raphaël Clifford, Zvi Gotthilf, Moshe Lewenstein, Alexandru Popa 0001	Restricted Common Superstring and Restricted Common Supersequence.	CPM	2011	DBLP DOI BibTeX RDF
24	Majid M. Naini, Joan F. Naini	The effect of vibrational frequencies on Humans and the Universe: a Transdisciplinary Approach Related to Superstring Theory.	Trans. SDPS	2010	DBLP BibTeX RDF
24	E. E. Escultura	Superstring interactions and computation.	Neural Parallel Sci. Comput.	2010	DBLP BibTeX RDF
24	Maxime Crochemore, Marek Cygan, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen	Algorithms for Three Versions of the Shortest Common Superstring Problem.	CPM	2010	DBLP DOI BibTeX RDF
24	Guowei Yang, Yonggui Kao, Yang Yang	The superstring galaxy associative memory model with anticipant fault-tolerant field on m-value information space.	ICNSC	2010	DBLP DOI BibTeX RDF
24	Zvi Gotthilf, Moshe Lewenstein, Alexandru Popa 0001	On Shortest Common Superstring and Swap Permutations.	SPIRE	2010	DBLP DOI BibTeX RDF
24	Bin Ma 0002	Why greed works for shortest common superstring problem.	Theor. Comput. Sci.	2009	DBLP DOI BibTeX RDF
24	Domingo López-Rodríguez, Enrique Mérida Casermeiro	Shortest Common Superstring Problem with Discrete Neural Networks.	ICANNGA	2009	DBLP DOI BibTeX RDF
24	Lucian Ilie, Cristian Popescu	The Shortest Common Superstring Problem and Viral Genome Compression.	Fundam. Informaticae	2006	DBLP BibTeX RDF
24	Maik Weinard, Georg Schnitger	On the Greedy Superstring Conjecture.	SIAM J. Discret. Math.	2006	DBLP DOI BibTeX RDF
24	J. T. Trevors	The Big Bang, Superstring Theory and the origin of life on the Earth.	Theory Biosci.	2006	DBLP DOI BibTeX RDF
24	Uli Laube, Maik Weinard	Erratum: "Conditional Inequalities And The Shortest Common Superstring Problem".	Int. J. Found. Comput. Sci.	2006	DBLP DOI BibTeX RDF
24	Lucas Ledesma, Daniel Manrique, Alfonso Rodríguez-Patón	A tissue P system and a DNA microfluidic device for solving the shortest common superstring problem.	Soft Comput.	2005	DBLP DOI BibTeX RDF
24	Uli Laube, Maik Weinard	Conditional inequalities and the shortest common superstring problem.	Int. J. Found. Comput. Sci.	2005	DBLP DOI BibTeX RDF
24	Uli Laube, Maik Weinard	Conditional Inequalities and the Shortest Common Superstring Problem.	Stringology	2004	DBLP BibTeX RDF
24	Chaomei Chen, Jasna Kuljis	The rising landscape: A visual exploration of superstring revolutions in physics.	J. Assoc. Inf. Sci. Technol.	2003	DBLP DOI BibTeX RDF
24	Ricky Robinson, Jadwiga Indulska	Superstring: a scalable service discovery protocol for the wide-area pervasive environment.	ICON	2003	DBLP DOI BibTeX RDF
24	Stephen Blaha	A Quantum Computer Foundation for the Standard Model and SuperString Theories	CoRR	2002	DBLP BibTeX RDF
24	Dirk Bongartz	On the Approximation Ratio of the Group-Merge Algorithm for the Shortest Common Superstring Problem.	Comput. Artif. Intell.	2001	DBLP BibTeX RDF
24	Mourad Elloumi	Algorithms for the shortest exact common superstring problem.	South Afr. Comput. J.	2000	DBLP BibTeX RDF
24	Greg Gloor, Lila Kari, Michelle Gaasenbeek, Sheng Yu 0001	Towards a DNA Solution to the Shortest Common Superstring Problem.	Int. J. Artif. Intell. Tools	1999	DBLP DOI BibTeX RDF
24	En-Hui Yang, Zhen Zhang 0010	The shortest common superstring problem: Average case analysis for both exact and approximate matching.	IEEE Trans. Inf. Theory	1999	DBLP DOI BibTeX RDF
24	Z. Sweedyk	A 2½-Approximation Algorithm for Shortest Superstring.	SIAM J. Comput.	1999	DBLP DOI BibTeX RDF
24	Alan M. Frieze, Wojciech Szpankowski	Greedy Algorithms for the Shortest Common Superstring That Are Asymptotically Optimal.	Algorithmica	1998	DBLP DOI BibTeX RDF
24	Chris Armen, Clifford Stein 0001	A 2 2/3 Superstring Approximation Algorithm.	Discret. Appl. Math.	1998	DBLP DOI BibTeX RDF
24	Chris Armen, Clifford Stein 0001	A 2 2/3-Approximation Algorithm for the Shortest Superstring Problem.	CPM	1996	DBLP DOI BibTeX RDF
24	Chris Armen, Clifford Stein 0001	Improved Length Bounds for the Shortest Superstring Problem (Extended Abstract).	WADS	1995	DBLP DOI BibTeX RDF
24	Dan Gusfield	Faster Implementation of a Shortest Superstring Approximation.	Inf. Process. Lett.	1994	DBLP DOI BibTeX RDF
24	Martin Middendorf	More on the Complexity of Common Superstring and Supersequence Problems.	Theor. Comput. Sci.	1994	DBLP DOI BibTeX RDF
24	C. D. Hurt, John M. Budd	Modeling the literature of superstring theory: A case of fast literature.	Scientometrics	1992	DBLP DOI BibTeX RDF
24	John M. Budd, C. D. Hurt	Superstring theory: Information transfer in an emerging field.	Scientometrics	1991	DBLP DOI BibTeX RDF
24	Jonathan S. Turner	Approximation Algorithms for the Shortest Common Superstring Problem	Inf. Comput.	1989	DBLP DOI BibTeX RDF
18	Mauro Francaviglia, Marcella Giulia Lorenzi, Michael Petry	Robotic Superstrings Installation: A-Life Science & Art.	ECAL	2007	DBLP DOI BibTeX RDF	A-Life Art, Robotics, Generative Art, Art and Science
18	Eva K. Lee, Todd Easton, Kapil Gupta	Novel evolutionary models and applications to sequence alignment problems.	Ann. Oper. Res.	2006	DBLP DOI BibTeX RDF	Evolutionary distance problem, Minimum weight common mutated sequence, Node-packing polytope, Multiple sequence alignment, DNA sequencing, Sequence comparison, Conflict graph, Supernode, Phylogenetic analysis
18	Kiyoko F. Aoki-Kinoshita, Minoru Kanehisa, Ming-Yang Kao, Xiang-Yang Li 0001, Weizhao Wang	A 6-Approximation Algorithm for Computing Smallest Common AoN-Supertree with Application to the Reconstruction of Glycan Trees.	ISAAC	2006	DBLP DOI BibTeX RDF
18	Qing Guo 0002, Hui Zhang 0004, Costas S. Iliopoulos	Computing the lambda-Seeds of a String.	AAIM	2006	DBLP DOI BibTeX RDF
18	Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko	Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs.	J. ACM	2005	DBLP DOI BibTeX RDF	Approximation algorithms
18	Assaf Zaritsky, Moshe Sipper	The preservation of favored building blocks in the struggle for fitness: the puzzle algorithm.	IEEE Trans. Evol. Comput.	2004	DBLP DOI BibTeX RDF