Finding common structured patterns in linear graphs

DOI10.1016/J.TCS.2010.02.017MaRDI QIDQ974741zbMATH OpenOpenAlexFDO

Authors Guillaume Fertin, Danny Hermelin, Romeo Rizzi, Stéphane Vialette

Publication date 7 June 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.02.017

zbMATH Keywords

approximationlinear graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Common Structured Patterns in Linear Graphs: Approximation and Combinatorics
• Approximation of RNA Multiple Structural Alignment
• Approximation of RNA multiple structural alignment
• Computing and Combinatorics
• On parameterized complexity of the multi-MCS problem

Cites work

• scientific article; zbMATH DE number 2185647 (Why is no real title available?)
• scientific article; zbMATH DE number 4108789 (Why is no real title available?)
• scientific article; zbMATH DE number 1305084 (Why is no real title available?)
• scientific article; zbMATH DE number 1333595 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 1954383 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2107707 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• A computational model for RNA multiple structural alignment
• A decomposition theorem for partially ordered sets
• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• Algorithms for the Longest Common Subsequence Problem
• Algorithms – ESA 2005
• An Optimal Decomposition Algorithm for Tree Edit Distance
• Approximation of RNA Multiple Structural Alignment
• Covering and coloring polygon-circle graphs
• Crossings and nestings of matchings and partitions
• Efficient algorithms for interval graphs and circular-arc graphs
• Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
• Extracting constrained 2-interval subsets in 2-interval sets
• Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs
• More Efficient Algorithm for Ordered Tree Inclusion
• On the computational complexity of 2-interval pattern matching problems
• On two open problems of 2-interval patterns
• Ordered and Unordered Tree Inclusion
• Pattern matching for permutations
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Sparse dynamic programming I
• The Complexity of Some Problems on Subsequences and Supersequences
• The longest common subsequence problem revisited
• What Makes the Arc-Preserving Subsequence Problem Hard?

Cited in

(3)

• Finding patterns in an unknown graph
• Near-Regular Structure Discovery Using Linear Programming
• Common Structured Patterns in Linear Graphs: Approximation and Combinatorics

This page was built for publication: Finding common structured patterns in linear graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974741)