Arşiv ve Dokümantasyon Merkezi
Dijital Arşivi

Graphs of edge-intersecting non-splitting paths

Basit öğe kaydını göster

dc.contributor Ph.D. Program in Industrial Engineering.
dc.contributor.advisor Aşıcı, Tınaz Ekim.
dc.contributor.author Boyacı, Arman.
dc.date.accessioned 2023-03-16T10:35:22Z
dc.date.available 2023-03-16T10:35:22Z
dc.date.issued 2015.
dc.identifier.other IE 2015 B67 PhD
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/13561
dc.description.abstract In this work, we introduce and study a new graph class: namely the graphs of Edge-Intersecting Non-Splitting Paths (ENP). First, we consider a special case where the host graph is a tree: the graphs of Edge-Intersecting Non-Splitting Paths in a Tree (ENPT). We study the characterization of the ENPT representations of chordless cycles (holes) which are one of the important basic graph structures. Under some assumption, we give an algorithm that returns the unique minimal representation if it exists. However, we show that the problem is NP-complete in general that is when this assumption does not necessarily hold. Then, we consider a more general case for which the host graph can be an arbitrary graph. As opposed to the Edge Intersection Graphs of Paths in an arbitrary graph which includes all graphs, we show that this is not true for ENP that is there exist some graphs which are not ENP. We also show that the class ENP coincides with the family of graphs of Edge-Intersecting and Non-Splitting Paths in a Grid (ENPG). Following similar studies for EPG graph class, we study the implications of restricting the number of bends of the individual paths in the grid. We show that restricting the number of bends also restricts the graph class. More concretely, by restricting the number of bends one gets an infinite sequence of classes such that every class is properly included in the next one. In particular, we show that one bend ENPG graphs are properly included in two bend ENPG graphs. In addition, we show that trees and cycles are one bend ENPG graphs, and characterize split graphs and co-bipartite graphs that are one bend ENPG. We prove that the recognition problem of one bend ENPG graphs is NP-complete even in a very restricted subclass of split graphs. Last, we provide a linear time recognition algorithm for one bend ENPG co-bipartite graphs.
dc.format.extent 30 cm.
dc.publisher Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2015.
dc.subject.lcsh Graph theory -- Data processing.
dc.title Graphs of edge-intersecting non-splitting paths
dc.format.pages xiii, 124 leaves ;


Bu öğenin dosyaları

Bu öğe aşağıdaki koleksiyon(lar)da görünmektedir.

Basit öğe kaydını göster

Dijital Arşivde Ara


Göz at

Hesabım