On the ordered list subgraph embedding problems

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

zbMATH Keywords

approximationgraph algorithms(classical) complexityordered subgraph embeddingparametrized complexityprotein/DNA structural comparison

Mathematics Subject Classification ID

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