[Date Prev][Date Next][Date Index]

# talk announcement Wed. 21 August 2013, Iyad Kanj "On the Ordered List Subgraph Embedding Problems"

• From: Beatrix Forsthuber <forst@dbai.tuwien.ac.at>
• Date: Wed, 21 Aug 2013 07:35:35 +0200
• User-agent: Mozilla/5.0 (Windows NT 5.1; rv:17.0) Gecko/20130509 Thunderbird/17.0.6

```
Dear all,

```
the Institute for Information Systems, Knowledge Based Systems Group cordially invites you to the following talk:
```

======================================================================

School of Computing, DePaul University
http://www.cdm.depaul.edu/soc/Pages/default2.aspx

======================================================================

DATE:  Wednesday, 21.8.2013
TIME:   11:30 am  s.t.
VENUE:  Seminarroom Goedel
(Favoritenstrasse 9-11, ground floor)

======================================================================

TITLE:   On the Ordered List Subgraph Embedding Problems

======================================================================

ABSTRACT:

```
In the parameterized Ordered List Subgraph Embedding problem (p-OLSE) we are given two graphs G and H, each with a linear order defined on its vertices, a function L that associates with every vertex in G a list of vertices in H, and a parameter k. The question is to decide if we can embed (one-to-one) a subgraph S of G of k vertices into H such that: (1) every vertex of S is mapped to a vertex from its associated list, (2) the linear orders inherited by S and its image under the embedding are respected, and (3) if there is an edge between two vertices in S then there is an edge between their images. If we require the subgraph S to be embedded as an induced subgraph, we obtain the Ordered List Induced Subgraph Embedding problem (p-OLISE). The p-OLSE and p-OLISE problems model various problems in Bioinformatics related to structural comparison/alignment of proteins.
```
```
We investigate the complexity of p-OLSE and p-OLISE with respect to the following structural parameters: the width of the function L (size of the largest list), and the maximum degree of H and G. We provide tight characterizations of the classical and parameterized complexity, and approximation of the problems with respect to the structural parameters under consideration.
```
======================================================================

```
With kind support of the Vienna Center for Logic and Algorithms VCLA (http://www.vcla.at/).
```

........................................................................

Thomas Eiter (prof)
Technische Universitaet Wien              tel: +43 1 58801 18460
Institut fuer Informationssysteme,        fax: +43 1 58801 18493
AB Wissensbasierte Systeme (184/3)      sec: +43 1 58801 18405
Favoritenstrasse 9-11, A-1040 Vienna    email: eiter@kr.tuwien.ac.at
AUSTRIA
http://www.kr.tuwien.ac.at/staff/eiter/                 DVR: 0005886
........................................................................

```