3 citations · 6 across the 5 of their papers we have counts for
4 papers · 1 filter
The Maximum Cardinality Cut Problem is Polynomial in Proper Interval Graphs
Arman Boyacı, Tinaz Ekim, Mordechai Shalom
It is known that the maximum cardinality cut problem is NP-hard even in chordal graphs. In this paper, we consider the time complexity of the problem in proper interval graphs, a s…
Graphs of Edge-Intersecting and Non-Splitting One Bend Paths in a Grid
Arman Boyacı, Tınaz Ekim, Mordechai Shalom +1
The families EPT (resp. EPG) Edge Intersection Graphs of Paths in a tree (resp. in a grid) are well studied graph classes. Recently we introduced the graph classes Edge-Intersectin…
Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes-Part II
Arman Boyacı, Tınaz Ekim, Mordechai Shalom +1
Given a tree and a set P of non-trivial simple paths on it, VPT(P) is the VPT graph (i.e. the vertex intersection graph) of the paths P, and EPT(P) is the EPT graph (i.e. the edge…
Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Towards Hole Representations-Part I
Arman Boyacı, Tınaz Ekim, Mordechai Shalom +1
Given a tree and a set of non-trivial simple paths on it, is the VPT graph (i.e. the vertex intersection graph) of the paths of the tree ,…