On the ordered list subgraph embedding problems
From MaRDI portal
Publication:270006
DOI10.1007/s00453-015-9980-2zbMath1332.68076arXiv1403.2009OpenAlexW2035955816MaRDI QIDQ270006
Olawale Hassan, Ljubomir Perković, Daniel Lokshtanov, Iyad A. Kanj
Publication date: 6 April 2016
Published in: Algorithmica, Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1403.2009
approximationgraph algorithms(classical) complexityordered subgraph embeddingparametrized complexityprotein/DNA structural comparison
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Incremental list coloring of graphs, parameterized by conservation
- Improved upper bounds for vertex cover
- The longest common subsequence problem for arc-annotated sequences
- Finding a maximum independent set in a permutation graph
- Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs
- Finding occurrences of protein complexes in protein-protein interaction graphs
- Optimization, approximation, and complexity classes
- The longest common subsequence problem for sequences with nested arc annotations.
- Computing the similarity of two sequences with nested arc annotations
- Parameterized intractability of distinguishing substring selection
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Color-coding
- Mathematical Foundations of Computer Science 2005
- Fundamentals of Computation Theory
This page was built for publication: On the ordered list subgraph embedding problems
