3 citations · 6 across the 5 of their papers we have counts for
3 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…
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…