On the public citation graph

Complexity of common subsequence and supersequence problems and related problems

https://doi.org/10.1007/bf01075212
0 signed · 113 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/978-1-4615-6666-3openalex-snapshot
Combinatorial Theory
inferredcites →https://doi.org/10.1007/978-3-319-44543-4openalex-snapshot
On Maximal Chain Subgraphs and Covers of Bipartite Graphs.
inferredcites →https://doi.org/10.1007/bf00264437openalex-snapshot
A longest common subsequence algorithm suitable for similar text strings
inferredcites →https://doi.org/10.1007/bf00265993openalex-snapshot
A linear space algorithm for the LCS problem
inferredcites →https://doi.org/10.1007/bf01117471openalex-snapshot
Real-time recognition of the inclusion relation
inferredcites →https://doi.org/10.1016/0012-365x(75)90103-xopenalex-snapshot
On computing the length of longest increasing subsequences
inferredcites →https://doi.org/10.1016/0020-0190(86)90091-8openalex-snapshot
A bit-string longest-common-subsequence algorithm
inferredcites →https://doi.org/10.1016/0020-0255(80)90025-0openalex-snapshot
A fast algorithm for the longest-common-subsequence problem
inferredcites →https://doi.org/10.1016/0022-0000(80)90002-1openalex-snapshot
A faster algorithm computing string edit distances
inferredcites →https://doi.org/10.1016/0022-0000(80)90004-5openalex-snapshot
On finding minimal length superstrings
inferredcites →https://doi.org/10.1016/0022-0000(84)90025-4openalex-snapshot
New algorithms for the LCS problem
inferredcites →https://doi.org/10.1016/0022-2836(70)90057-4openalex-snapshot
A general method applicable to the search for similarities in the amino acid sequence of two proteins
inferredcites →https://doi.org/10.1016/0022-2836(73)90369-0openalex-snapshot
A test for nucleotide sequence homology
inferredcites →https://doi.org/10.1016/0022-5193(65)90096-2openalex-snapshot
Computer aids to protein sequence determination
inferredcites →https://doi.org/10.1016/0097-3165(74)90050-8openalex-snapshot
An algorithm for the distance between two finite sequences
inferredcites →https://doi.org/10.1016/0167-8191(86)90021-9openalex-snapshot
The mapping of 2-D array processors to 1-D array processors
inferredcites →https://doi.org/10.1016/0304-3975(76)90062-1openalex-snapshot
Complete sets and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0898-1221(78)90043-3openalex-snapshot
Combinatorial algorithms: Theory and practice
inferredcites →https://doi.org/10.1038/scientificamerican0769-86openalex-snapshot
Computer Analysis of Protein Evolution
inferredcites →https://doi.org/10.1109/swat.1973.13openalex-snapshot
Linear pattern matching algorithms
inferredcites →https://doi.org/10.1109/tsmc.1978.4309979openalex-snapshot
A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
inferredcites →https://doi.org/10.1145/321796.321811openalex-snapshot
The String-to-String Correction Problem
inferredcites →https://doi.org/10.1145/321879.321880openalex-snapshot
An Extension of the String-to-String Correction Problem
inferredcites →https://doi.org/10.1145/321921.321922openalex-snapshot
Bounds on the Complexity of the Longest Common Subsequence Problem
inferredcites →https://doi.org/10.1145/321921.321923openalex-snapshot
Bounds for the String Editing Problem
inferredcites →https://doi.org/10.1145/321941.321946openalex-snapshot
A Space-Economical Suffix Tree Construction Algorithm
inferredcites →https://doi.org/10.1145/322033.322044openalex-snapshot
Algorithms for the Longest Common Subsequence Problem
inferredcites →https://doi.org/10.1145/322063.322075openalex-snapshot
The Complexity of Some Problems on Subsequences and Supersequences
inferredcites →https://doi.org/10.1145/322234.322237openalex-snapshot
Linear Algorithm for Data Compression via String Matching
inferredcites →https://doi.org/10.1145/322234.322244openalex-snapshot
String Matching in Real Time
inferredcites →https://doi.org/10.1145/359581.359603openalex-snapshot
A fast algorithm for computing longest common subsequences
inferredcites →https://doi.org/10.1145/360825.360861openalex-snapshot
A linear space algorithm for computing maximal common subsequences

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/047134608x.w8330openalex-snapshot
Memetic Algorithms: A Contemporary Introduction
inferred← citeshttps://doi.org/10.1002/9780470892107.ch2openalex-snapshot
Efficient Restricted‐Case Algorithms for Problems in Computational Biology
inferred← citeshttps://doi.org/10.1007/11494669_7openalex-snapshot
A Comparison of Evolutionary Approaches to the Shortest Common Supersequence Problem
inferred← citeshttps://doi.org/10.1007/11499305_9openalex-snapshot
Memetic Algorithms with Partial Lamarckism for the Shortest Common Supersequence Problem
inferred← citeshttps://doi.org/10.1007/3-540-58094-8_16openalex-snapshot
Maximal common subsequences and minimal common supersequences
inferred← citeshttps://doi.org/10.1007/3-540-58201-0_68openalex-snapshot
On the approximation of shortest common supersequences and longest common subsequences
inferred← citeshttps://doi.org/10.1007/3-540-58325-4_194openalex-snapshot
On the approximation of finding various minimal, maximal, and consistent sequences
inferred← citeshttps://doi.org/10.1007/3-540-60044-2_34openalex-snapshot
Common subsequences and supersequences and their expected length
inferred← citeshttps://doi.org/10.1007/978-1-4613-3629-7_10openalex-snapshot
Optimization Problems in Molecular Biology
inferred← citeshttps://doi.org/10.1007/978-1-4939-0808-0_10openalex-snapshot
The Shortest Superstring Problem
inferred← citeshttps://doi.org/10.1007/978-3-031-04148-8_9openalex-snapshot
A Beam Search for the Shortest Common Supersequence Problem Guided by an Approximate Expected Length Calculation
inferred← citeshttps://doi.org/10.1007/978-3-540-71615-0_4openalex-snapshot
A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem
inferred← citeshttps://doi.org/10.1007/978-3-540-78295-7_4openalex-snapshot
Hybridizations of Metaheuristics With Branch & Bound Derivates
inferred← citeshttps://doi.org/10.1007/978-3-540-89097-3_25openalex-snapshot
Some Approximations for Shortest Common Nonsubsequences and Supersequences
inferred← citeshttps://doi.org/10.1007/978-3-642-03784-9_27openalex-snapshot
Improved Approximation Results on the Shortest Common Supersequence Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-24583-1_6openalex-snapshot
Weighted Shortest Common Supersequence
inferred← citeshttps://doi.org/10.1007/978-3-642-32615-8_40openalex-snapshot
An Ant-Colony Algorithm to Transform Jobshops into Flowshops: A Case of Shortest-Common-Supersequence Stringology Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-51175-2_38openalex-snapshot
Alignment, Comparison and Consensus of Molecular Sequences
inferred← citeshttps://doi.org/10.1007/978-3-642-56656-1_13openalex-snapshot
Solving the Shortest Common Supersequence Problem
inferred← citeshttps://doi.org/10.1007/978-4-431-65950-1_14openalex-snapshot
Towards Comparison of Decomposable Systems
inferred← citeshttps://doi.org/10.1007/978-981-16-2774-3_6openalex-snapshot
A Deterministic Heuristic Algorithm to Minimize the Length of a Manufacturing Line in Transformation of Jobshops into Flowshops
inferred← citeshttps://doi.org/10.1007/bf01545528openalex-snapshot
Improved heuristics and a genetic algorithm for finding short supersequences
inferred← citeshttps://doi.org/10.1007/bfb0029797openalex-snapshot
On the worst-case behaviour of some approximation algorithms for the shortest common supersequence of k strings
inferred← citeshttps://doi.org/10.1007/bfb0056911openalex-snapshot
An island model based ant system with lookahead for the shortest supersequence problem
inferred← citeshttps://doi.org/10.1007/s00224-011-9339-2openalex-snapshot
The Complexity of Flood Filling Games
inferred← citeshttps://doi.org/10.1007/s002240010011openalex-snapshot
On the Flattest Common Supersequence Method for Deadlock-Free Routing in Arbitrary Networks
inferred← citeshttps://doi.org/10.1007/s00453-007-0080-9openalex-snapshot
Polynomial-Time Algorithms for the Ordered Maximum Agreement Subtree Problem
inferred← citeshttps://doi.org/10.1007/s10479-006-0151-3openalex-snapshot
Minimum cost multi-product flow lines
inferred← citeshttps://doi.org/10.1016/0020-0190(91)90094-xopenalex-snapshot
On the inadequacy of tournament algorithms for the N-SCS problem
inferred← citeshttps://doi.org/10.1016/0303-2647(93)90064-jopenalex-snapshot
Non-similarity combinatorial problems
inferred← citeshttps://doi.org/10.1016/0304-3975(92)00074-2openalex-snapshot
More on the complexity of common superstring and supersequence problems
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90200-dopenalex-snapshot
The shortest common nonsubsequence problem is NP-complete
inferred← citeshttps://doi.org/10.1016/0304-3975(94)00257-jopenalex-snapshot
On the approximation of longest common nonsupersequences and shortest common nonsubsequences
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00014-nopenalex-snapshot
On finding minimal, maximal, and consistent sequences over a binary alphabet
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00138-7openalex-snapshot
Consistent subsequences and supersequences
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00185-9openalex-snapshot
Two-Dimensional partitioning problems
inferred← citeshttps://doi.org/10.1016/0304-3975(95)80013-1openalex-snapshot
Shortest consistent superstrings computable in polynomial time
inferred← citeshttps://doi.org/10.1016/j.aam.2019.01.004openalex-snapshot
Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies
inferred← citeshttps://doi.org/10.1016/j.cie.2004.05.010openalex-snapshot
A heuristic approach to batching and scheduling a single machine to minimize setup costs
inferred← citeshttps://doi.org/10.1016/j.cie.2006.10.001openalex-snapshot
An adaptive branch and bound approach for transforming job shops into flow shops
inferred← citeshttps://doi.org/10.1016/j.compbiolchem.2016.05.004openalex-snapshot
Chemical reaction optimization for solving shortest common supersequence problem
inferred← citeshttps://doi.org/10.1016/j.compbiolchem.2020.107327openalex-snapshot
An improved chemical reaction optimization algorithm for solving the shortest common supersequence problem
inferred← citeshttps://doi.org/10.1016/j.dam.2020.10.012openalex-snapshot
The Multi-Spreader Crane Scheduling Problem: Partitions and supersequences
inferred← citeshttps://doi.org/10.1016/j.engappai.2011.08.006openalex-snapshot
An enhanced beam search algorithm for the Shortest Common Supersequence Problem
inferred← citeshttps://doi.org/10.1016/j.ipl.2009.06.010openalex-snapshot
Finding the longest common nonsuperstring in linear time
inferred← citeshttps://doi.org/10.1016/j.jcss.2024.103546openalex-snapshot
The tree-child network inference problem for line trees and the shortest common supersequence problem for permutation strings
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.02.001openalex-snapshot
Combined super-/substring and super-/subsequence problems
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.10.002openalex-snapshot
Longest common subsequence problem for unoriented and cyclic strings
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.05.029openalex-snapshot
Multiple genome rearrangement by swaps and by element duplications
inferred← citeshttps://doi.org/10.1016/j.tcs.2015.02.008openalex-snapshot
Tractability and hardness of flood-filling games on trees
inferred← citeshttps://doi.org/10.1016/j.tcs.2024.114889openalex-snapshot
String editing under pattern constraints
inferred← citeshttps://doi.org/10.1016/s0196-6774(03)00081-6openalex-snapshot
Analogs & duals of the MAST problem for sequences & trees
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00085-3openalex-snapshot
An approximate A∗ algorithm and its application to the SCS problem
inferred← citeshttps://doi.org/10.1017/s096354839800368xopenalex-snapshot
Common Subsequences and Supersequences and their Expected Length
inferred← citeshttps://doi.org/10.1023/a:1009827520712openalex-snapshot
Transversal Graphs for Partially Ordered Sets: Sequencing, Merging and Scheduling Problems
inferred← citeshttps://doi.org/10.1023/a:1022239620866openalex-snapshot
Part Batching and Scheduling in a Flexible Cell to Minimize Setup Costs
inferred← citeshttps://doi.org/10.1080/00207543.2013.876114openalex-snapshot
Sequencing a batching flexible cell to minimise set-up costs
inferred← citeshttps://doi.org/10.1080/07408170008963907openalex-snapshot
Minimal investment budgets for flow line configuration
inferred← citeshttps://doi.org/10.1080/07408170590918191openalex-snapshot
Efficient heuristic approaches to transform job shops into flow shops
inferred← citeshttps://doi.org/10.1089/cmb.1998.5.173openalex-snapshot
Sequence Alignment in Molecular Biology
inferred← citeshttps://doi.org/10.1090/dimacs/047/05openalex-snapshot
Sequence alignment in molecular biology
inferred← citeshttps://doi.org/10.1093/bioinformatics/11.1.49openalex-snapshot
Parameterized complexity analysis in computational biology
inferred← citeshttps://doi.org/10.1109/dsn.2016.21openalex-snapshot
Can't Touch This: Consistent Network Updates for Multiple Policies
inferred← citeshttps://doi.org/10.1109/icde.2003.1260793openalex-snapshot
Efficient creation of statistics over query expressions
inferred← citeshttps://doi.org/10.1109/iciev.2016.7760187openalex-snapshot
Solving shortest common supersequence problem using chemical reaction optimization
inferred← citeshttps://doi.org/10.1109/ipdps.2011.111openalex-snapshot
Offline Scheduling of Multi-threaded Request Streams on a Caching Server
inferred← citeshttps://doi.org/10.1109/recosoc.2014.6861352openalex-snapshot
An application scenario for dynamically reconfigurable FPGAs
inferred← citeshttps://doi.org/10.1109/spire.1999.796596openalex-snapshot
Problems related to subsequences and supersequences
inferred← citeshttps://doi.org/10.1109/tnet.2018.2810640openalex-snapshot
Efficient Loop-Free Rerouting of Multiple SDN Flows
inferred← citeshttps://doi.org/10.1109/tnet.2020.2979400openalex-snapshot
New Alternatives to Optimize Policy Classifiers
inferred← citeshttps://doi.org/10.1137/s0895480192234277openalex-snapshot
String Noninclusion Optimization Problems
inferred← citeshttps://doi.org/10.1145/1830483.1830529openalex-snapshot
Efficient stochastic local search algorithm for solving the shortest common supersequence problem
inferred← citeshttps://doi.org/10.1145/2001576.2001620openalex-snapshot
Evolutionary-based iterative local search algorithm for the shortest common supersequence problem
inferred← citeshttps://doi.org/10.1145/277651.277671openalex-snapshot
Deadlock-free routing in arbitrary networks via the flattest common supersequence method
inferred← citeshttps://doi.org/10.1145/3196883openalex-snapshot
Inferring Extended Probabilistic Finite-State Automaton Models from Software Executions
inferred← citeshttps://doi.org/10.1371/journal.pone.0052427openalex-snapshot
A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem
inferred← citeshttps://doi.org/10.3390/e24050641openalex-snapshot
An Opposition-Based Learning CRO Algorithm for Solving the Shortest Common Supersequence Problem
inferred← citeshttps://doi.org/10.48550/arxiv.1001.4420openalex-snapshot
The Complexity of Flood Filling Games
inferred← citeshttps://doi.org/10.48550/arxiv.1111.5442openalex-snapshot
Improved Lower Bounds for the Shortest Superstring and Related Problems
inferred← citeshttps://doi.org/10.48550/arxiv.1111.6983openalex-snapshot
Aggregation of Composite Solutions: strategies, models, examples
inferred← citeshttps://doi.org/10.5555/642129.642130openalex-snapshot
Approximation algorithms for the shortest common supersequence
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.