• English
    • Türkçe
  • Türkçe 
    • English
    • Türkçe
  • Giriş
Öğe Göster 
  •   E-arşiv Ana Sayfası
  • Akademik Arşiv / Institutional Repository
  • Mühendislik Fakültesi / Faculty of Engineering
  • Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering
  • Öğe Göster
  •   E-arşiv Ana Sayfası
  • Akademik Arşiv / Institutional Repository
  • Mühendislik Fakültesi / Faculty of Engineering
  • Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering
  • Öğe Göster
JavaScript is disabled for your browser. Some features of this site may not work without it.

Structure of conflict graphs in constraint alignment problems and algorithms

Thumbnail
Göster/Aç
Structure of conflict graphs in constraint alignment problems and algorithms (645.7Kb)
Tarih
2019
Yazar
Alkan, Ferhat
Bıyıkoğlu, Türker
Demange, Marc
Erten, Cesim
Üst veri
Tüm öğe kaydını göster
Özet
We consider the constrained graph alignment problem which has applications in biological network analysis. Given two input graphs G1 = (V1, E1), G2 = (V2, E2), two vertices u1, v1 of G1 paired respectively to two vertices u2, v2 of G2 induce an edge conservation if u1, v1 and u2, v2 are adjacent in their respective graphs. The goal is to provide a one-to-one mapping between some vertices of the input graphs in order to maximize edge conservation. However the allowed mappings are restricted since each vertex from V1 (resp. V2) is allowed to be mapped to at most m1 (resp. m2) specified vertices in V2 (resp. V1). Most of the results in this paper deal with the case m2 = 1 which attracted most attention in the related literature. We formulate the problem as a maximum independent set problem in a related conflict graph and investigate structural properties of this graph in terms of forbidden subgraphs. We are interested, in particular, in excluding certain wheels, fans, cliques or claws (all terms are defined in the paper), which in turn corresponds to excluding certain cycles, paths, cliques or independent sets in the neighborhood of each vertex. Then, we investigate algorithmic consequences of some of these properties, which illustrates the potential of this approach and raises new horizons for further works. In particular this approach allows us to reinterpret a known polynomial case in terms of conflict graph and to improve known approximation and fixed-parameter tractability results through efficiently solving the maximum independent set problem in conflict graphs. Some of our new approximation results involve approximation ratios that are functions of the optimal value, in particular its square root; this kind of results cannot be achieved for maximum independent set in general graphs.
Bağlantı
http://hdl.handle.net/20.500.12566/460
Koleksiyonlar
  • Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering
  • WOS İndeksli Yayınlar Koleksiyonu

İlgili Öğeler

Başlık, yazar, küratör ve konuya göre gösterilen ilgili öğeler.

  • Optimizing the liver/kidney organ donation waiting list in Antalya using maxsat and graph model 

    Ülgen, Semail; Yangın, Elifnaz (International Conference on Industrial Engineering and Operations Management, 2022)
    Organ transplantation has become an increasing need in the world and in our country. Organ transplantation is completed by taking healthy and matched organs from living or cadaver donors and transplanting them to the ...
  • Graph-theoretical comparison of normal and tumor networks in identifying BRCA genes 

    Erten, Cesim; Dopazo, Joaquin (BMC Systems Biology, 2017)
    Background: Identification of driver genes related to certain types of cancer is an important research topic. Several systems biology approaches have been suggested, in particular for the identification of breast cancer ...
  • A graph theoretical approach for aligning cell lines and tumors 

    Akay, Muhammet Edip (Antalya Bilim Üniversitesi Lisansüstü Eğitim Enstitüsü, 2022)
    Cell line have now been shown in lots of research to be the most important primary tool for preclinical cancer research, but their representative quality in patient tumor samples remains unclear. The comparison of RNA-seq ...

DSpace software copyright © 2002-2016  DuraSpace
İletişim | Geri Bildirim
Theme by 
Atmire NV
 

 




sherpa/romeo


Göz at

Tüm E-arşivBölümler & KoleksiyonlarTarihe GöreYazara GöreBaşlığa GöreKonuya GöreTüre GöreABU Yazarına GöreWOSScopusPubMedTRDizinErişimBu KoleksiyonTarihe GöreYazara GöreBaşlığa GöreKonuya GöreTüre GöreABU Yazarına GöreWOSScopusPubMedTRDizinErişim

Hesabım

GirişKayıt

DSpace software copyright © 2002-2016  DuraSpace
İletişim | Geri Bildirim
Theme by 
Atmire NV
 

 


|| Kütüphane || Antalya Bilim Üniversitesi || OAI-PMH ||

Antalya Bilim Üniversitesi Kütüphane ve Dokümantasyon Müdürlüğü, Antalya, Turkey
İçerikte herhangi bir hata görürseniz, lütfen bildiriniz: acikerisim@antalya.edu.tr

E-arşiv@AntalyaBilim:


DSpace 6.4-SNAPSHOT

Gemini Bilgi Teknolojileri A.Ş tarafından destek verilmektedir.