Fatemeh Keshavarz-Kohjerdi

Dr. Fatemeh Keshavarz-Kohjerdi

orcid

Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
13 February 2022 in Algorithms
Verified
Journal Article
Open access
PDF file
FKFatemeh Keshavarz-Kohjerdi
Fatemeh Keshavarz-Kohjerdi
Ruo-Wei HungRuo-Wei Hung
Ruo-Wei Hung
A graph is called Hamiltonian connected if it contains a Hamiltonian path between any two distinct vertices. In the past, we proved the Hamiltonian path and cycle problems for general supergrid graphs to be NP-complete. However, they are still open for solid supergrid graphs. In this paper, first we will verify the Hamiltonian cycle property of C-shaped supergrid graphs, which are a special case of solid supergrid graphs. Next, we show that C-shaped supergrid graphs are Hamiltonian connected except in a few conditions. For these excluding conditions of Hamiltonian connectivity, we compute their longest paths. Then, we design a linear-time algorithm to solve the longest path problem in these graphs. The Hamiltonian connectivity of C-shaped supergrid graphs can be applied to compute the optimal stitching trace of computer embroidery machines, and construct the minimum printing trace of 3D printers with a C-like component being printed.

30 October 2022 in Algorithms
Verified
Journal Article
Open access
PDF file
JCJong-Shin Chen
Jong-Shin Chen
Ruo-Wei HungRuo-Wei Hung
Ruo-Wei Hung
FKFatemeh Keshavarz-Kohjerdi
Fatemeh Keshavarz-Kohjerdi
Yung-Fa HuangYung-Fa Huang
Yung-Fa Huang
Supergrid graphs are derived by computing stitch paths for computerized embroidery machines. In the past, we have studied the Hamiltonian-related properties of supergrid graphs and their subclasses of graphs. In this paper, we propose a generalized graph class for supergrid graphs called extended supergrid graphs. Extended supergrid graphs include grid graphs, supergrid graphs, diagonal supergrid graphs, and triangular supergrid graphs as subclasses of graphs. In this paper, we study the problems of domination and independent domination on extended supergrid graphs. A dominating set of a graph is the subset of vertices on it, such that every vertex of the graph is in this set or adjacent to at least a vertex of this set. If any two vertices in a dominating set are not adjacent, this is called an independent dominating set. Domination and independent domination problems find a dominating set and an independent dominating set with the least number of vertices on a graph, respectively. The domination and independent domination set problems on grid graphs are known to be NP-complete, meaning that these two problems on extended supergrid graphs are also NP-complete. However, the complexities of these two problems in other subclasses of graphs remain unknown. In this paper, we first prove that these two problems on diagonal supergrid graphs are NP-complete, then, by a simple extension, we prove that these two problems on supergrid graphs and triangular supergrid graphs are also NP-complete. In addition, these two problems on rectangular supergrid graphs are known to be linearly solvable; however, the complexities of these two problems on rectangular triangular-supergrid graphs remain unknown. This paper provides tight upper bounds on the sizes of the minimum dominating and independent dominating sets for rectangular triangular-supergrid graphs.

16 August 2024 in IEEE Transactions on Parallel and Distributed Systems
Verified
Journal Article
Closed access
FKFatemeh Keshavarz-Kohjerdi
Fatemeh Keshavarz-Kohjerdi
In the paired many-to-many $k$ -disjoint path cover ( $k$ -DPC) problem, given a set of $k$ pairs of vertices $(s_{i},t_{i})$ , $1\leqslant i\leqslant k$ , of a graph $G$ we want to find $k$ simple vertex-disjoint paths whose end-vertices are these $k$ pairs, such that each vertex of $G$ is covered by a path. This problem is a well-known problem in parallel processing and is a generalization of the well-known Hamiltonian $(s,t)$ -path problem, which is equal to 1-DPC. In this paper, we consider the paired many-to-many 2-disjoint path cover problem (2-DPC) in meshes (rectangular grids). We give the necessary conditions for existence of such covers, and present a linear-time algorithm to compute them. Although the paired many-to-many $k$ -disjoint path cover problem is well-known in parallel processing, our motivation to study this problem is its application in solving the Hamiltonian path problem in solid grid graphs. We consider the case where the pairs of vertices are on the outer face of the graph.

15 June 2023 in Mathematics
Verified
Journal Article
Open access
PDF file
FKFatemeh Keshavarz-Kohjerdi
Fatemeh Keshavarz-Kohjerdi
Ruo-Wei HungRuo-Wei Hung
Ruo-Wei Hung
The longest (s,t)-path problem on supergrid graphs is known to be NP-complete. However, the complexity of this problem on supergrid graphs with or without holes is still unknown.In the past, we presented linear-time algorithms for solving the longest (s,t)-path problem on L-shaped and C-shaped supergrid graphs, which form subclasses of supergrid graphs without holes. In this paper, we will determine the complexity of the longest (s,t)-path problem on O-shaped supergrid graphs, which form a subclass of supergrid graphs with holes. These graphs are rectangular supergrid graphs with rectangular holes. It is worth noting that O-shaped supergrid graphs contain L-shaped and C-shaped supergrid graphs as subgraphs, but there is no inclusion relationship between them. We will propose a linear-time algorithm to solve the longest (s,t)-path problem on O-shaped supergrid graphs. The longest (s,t)-paths of O-shaped supergrid graphs have applications in calculating the minimum trace when printing hollow objects using computer embroidery machines and 3D printers.

19 April 2018 in Optimization Methods and Software
Verified
Journal Article
Closed access
FKFatemeh Keshavarz-Kohjerdi
Fatemeh Keshavarz-Kohjerdi
ABAlireza Bagheri
Alireza Bagheri
The longest path problem, that is, finding a simple path with the maximum number of vertices, is a well-known NP-hard problem with many applications. However, for some classes of graphs, including solid grid graphs and grid graphs with some holes, it is open. An L-shaped grid graph is a special kind of a rectangular grid graph with a rectangular hole. In this paper, we show that a longest path between two given vertices s and t of an L-shaped grid graph can be computed in linear time.

2 June 2021 in The Journal of Supercomputing
Verified
Journal Article
Closed access
PDF file
FKFatemeh Keshavarz-Kohjerdi
Fatemeh Keshavarz-Kohjerdi