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

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




Dear all,

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


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

Speaker: Iyad Kanj
              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
  ........................................................................