2007 | OriginalPaper | Buchkapitel
Common Structured Patterns in Linear Graphs: Approximation and Combinatorics
verfasst von : Guillaume Fertin, Danny Hermelin, Romeo Rizzi, Stéphane Vialette
Erschienen in: Combinatorial Pattern Matching
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A linear graph is a graph whose vertices are linearly ordered. This linear ordering allows pairs of disjoint edges to be either preceding (<), nesting (
$\sqsubset$
) or crossing (
$\between$
). Given a family of linear graphs, and a non-empty subset
$\mathcal{R} \subseteq \{<,\sqsubset,\between\}$
, we are interested in the PBMCSP problem: Find a maximum size edge-disjoint graph, with edge-pairs all comparable by one of the relations in
$\mathcal{R}$
, that occurs as a subgraph in each of the linear graphs of the family. In this paper, we generalize the framework of Davydov and Batzoglou by considering patterns comparable by all possible subsets
$\mathcal{R} \subseteq \{<,\sqsubset,\between\}$
. This is motivated by the fact that many biological applications require considering crossing structures, and by the fact that different combinations of the relations above give rise to different generalizations of natural combinatorial problems. Our results can be summarized as follows: We give tight hardness results for the PBMCSP problem for
$\{<,\between\}$
-structured patterns and
$\{\sqsubset,\between\}$
-structured patterns. Furthermore, we prove that the problem is approximable within ratios: (
i
)
for
$\{<,\between\}$
-structured patterns, (
ii
)
k
1/2
for
$\{\sqsubset, \between\}$
-structured patterns, and (
iii
)
$\mathcal{O}(\sqrt{k \lg k})$
for
$\{<,\sqsubset,\between\}$
-structured patterns, where
k
is the size of the optimal solution and
is the
k
-th harmonic number.