3 citations · 6 across the 5 of their papers we have counts for
6 papers
On the Maximum Cardinality Cut Problem in Proper Interval Graphs and Related Graph Classes
Arman Boyacı, Tınaz Ekim, Mordechai Shalom
Although it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be…
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…
The Maximum Cut Problem in Co-bipartite Chain Graphs
Arman Boyacı, Tınaz Ekim, Mordechai Shalom
A \emph{co-bipartite chain} graph is a co-bipartite graph in which the neighborhoods of the vertices in each clique can be linearly ordered with respect to inclusion. It is known t…
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 ,…