CATALOGO DEI PRODOTTI DELLA RICERCA
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishA linear graph is a graph whose vertices are linearly ordered. This linear ordering allows pairs of disjoint edges to be either preceding (<), nesting ( N ) or crossing ( C ). Given a family of linear graphs, and a non-empty subset R ⊆ {<, N, C}, we are interested in the Maximum Common Structured Pattern (MCSP) problem: find a maximum size edge-disjoint graph, with edge-pairs all comparable by one of the relations in R, that occurs as a subgraph in each of the linear graphs of the family. The MCSP problem generalizes many structure-comparison and structure-prediction problems that arise in computational molecular biology. We give tight hardness results for the MCSP problem for {<, C }-structured pat- terns and { N, C }-structured patterns. Furthermore, we prove that the problem is approximable within ratios: (i) 2H (k) for {<, C }-structured patterns, (ii) √k for { N, C }-structured patterns, and (iii) O( √(k log k) ) for {<, N, C }-structured patterns, where k is the size of the optimal solution and H (k) is the k-th harmonic number. Also, we provide combinatorial results concerning the different types of structured patterns that are of independent interest in their own right.
| Titolo: | Common Structured Patterns in Linear Graphs: Approximation and Combinatorics |
| Autori: | |
| Data di pubblicazione: | 2007 |
| Abstract: | A linear graph is a graph whose vertices are linearly ordered. This linear ordering allows pairs of disjoint edges to be either preceding (<), nesting ( N ) or crossing ( C ). Given a family of linear graphs, and a non-empty subset R ⊆ {<, N, C}, we are interested in the Maximum Common Structured Pattern (MCSP) problem: find a maximum size edge-disjoint graph, with edge-pairs all comparable by one of the relations in R, that occurs as a subgraph in each of the linear graphs of the family. The MCSP problem generalizes many structure-comparison and structure-prediction problems that arise in computational molecular biology. We give tight hardness results for the MCSP problem for {<, C }-structured pat- terns and { N, C }-structured patterns. Furthermore, we prove that the problem is approximable within ratios: (i) 2H (k) for {<, C }-structured patterns, (ii) √k for { N, C }-structured patterns, and (iii) O( √(k log k) ) for {<, N, C }-structured patterns, where k is the size of the optimal solution and H (k) is the k-th harmonic number. Also, we provide combinatorial results concerning the different types of structured patterns that are of independent interest in their own right. |
| Handle: | http://hdl.handle.net/11562/409580 |
| ISBN: | 9783540734369 |
| Appare nelle tipologie: | 04.01 Contributo in atti di convegno |
File in questo prodotto:
http://hdl.handle.net/11562/409580
Copyright © 2021