[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:
`
======================================================================
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
........................................................................