7 citations · 17 across the 16 of their papers we have counts for
19 papers
Generation of weighted trees, block trees and block graphs
Tınaz Ekim, Mordechai Shalom, Mehmet Aziz Yirik
We present a general framework to generate trees every vertex of which has a non-negative weight and a color. The colors are used to impose certain restrictions on the weight and c…
Defensive Domination in Proper Interval Graphs
Tınaz Ekim, Arthur Farley, Andrzej Proskurowski +1
-defensive domination, a variant of the classical domination problem on graphs, seeks a minimum cardinality vertex set providing a surjective defense against any attack on verti…
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 Complexity of Subtree Intersection Representation of Chordal Graphs and Linear Time Chordal Graph Generation
Tınaz Ekim, Mordechai Shalom, Oylum Şeker
It is known that any chordal graph on vertices can be represented as the intersection of subtrees in a tree on nodes. This fact is recently used in [2] to generate rand…
Hierarchical b-Matching
Yuval Emek, Shay Kutten, Mordechai Shalom +1
A matching of a graph is a subset of edges no two of which share a common vertex, and a maximum matching is a matching of maximum cardinality. In a -matching every vertex ha…
Multicast Communications in Tree Networks with Heterogeneous Capacity Constraints
Yuval Emek, Shay Kutten, Mordechai Shalom +1
A widely studied problem in communication networks is that of finding the maximum number of communication requests that can be scheduled concurrently, subject to node and/or link c…
Minimum Reload Cost Graph Factors
Julien Baste, Didem Gözüpek, Mordechai Shalom +1
The concept of Reload cost in a graph refers to the cost that occurs while traversing a vertex via two of its incident edges. This cost is uniquely determined by the colors of the…
Parameterized complexity of finding a spanning tree with minimum reload cost diameter
Julien Baste, Didem Gözüpek, Christophe Paul +3
We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirect…
On two extensions of equimatchable graphs
Zakir Deniz, Tınaz Ekim, Tatiana Romina Hartinger +2
A graph is said to be equimatchable if all its maximal matchings are of the same size. In this work we introduce two extensions of the property of equimatchability by defining two…
Edge Coloring with Minimum Reload/Changeover Costs
Didem Gözüpek, Mordechai Shalom
In an edge-colored graph, a traversal cost occurs at a vertex along a path when consecutive edges with different colors are traversed. The value of the traversal cost depends only…
Equimatchable Claw-Free Graphs
Saieed Akbari, Hadi Alizadeh, Tınaz Ekim +2
A graph is equimatchable if all of its maximal matchings have the same size. A graph is claw-free if it does not have a claw as an induced subgraph. In this paper, we provide, to t…
A Simple Extension of Dirac's Theorem on Hamiltonicity
Yasemin Büyükçolak, Didem Gözüpek, Sibel Özkan +1
The classical Dirac theorem asserts that every graph on vertices with minimum degree is Hamiltonian. The lower bound of on…
Parameterized complexity of the MINCCA problem on graphs of bounded decomposability
Didem Gözüpek, Sibel Özkan, Christophe Paul +2
In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The "Minimum Chan…
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 ,…
Online Regenerator Placement
George B. Mertzios, Mordechai Shalom, Prudence W. H. Wong +1
Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most hops,…