Saeed Mehrabi
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Saeed Mehrabi has a total of 26 co-authors. Here are the top co-authors by number of shared publications:
- Anil Maheshwari
School of Computer Science, Carleton University, Ottawa, Canada
3 shared publications - Debajyoti Mondal
University of Saskatchewan
3 shared publications - Stephane Durocher
University of Manitoba
3 shared publications J. Mark Keil
2 shared publications- Ahmad Biniaz
School of Computer Science, University of Windsor, Windsor, Canada
1 shared publication Ali D. Mehrabi
Eindhoven University of Technology
1 shared publication
Latest Publications
- 16 December 2023
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 33 (03n04) , 133-157
Maximum Bipartite Subgraphs of Geometric Intersection Graphs
We study the Maximum Bipartite Subgraph ([ ]) problem, which is defined as follows. Given a set [ ] of [ ] geometric objects in the plane, we want to compute a maximum-size subset [ ] such that the intersection graph of the objects in [ ] is bipartite. We first give an [ ]-time algorithm that computes an almost optimal solution for the problem on circular-arc graphs. We show that the [ ] problem is [ ]-hard on geometric graphs for which the maximum independent set is [ ]-hard (hence, it is [ ]-hard even on unit squares and unit disks). On the other hand, we give a [ ] for the problem on unit squares and unit disks. Moreover, we show fast approximation algorithms with small-constant factors for the problem on unit squares, unit disks, and unit-height axis parallel rectangles. Additionally, we prove that the Maximum Triangle-free Subgraph ([ ]) problem is NP-hard for axis-parallel rectangles. Here the objective is the same as that of the [ ] except the intersection graph induced by the set [ ] needs to be triangle-free only (instead of being bipartite).
- 16 December 2023
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 33 (03n04) , 133-157
Maximum Bipartite Subgraphs of Geometric Intersection Graphs
We study the Maximum Bipartite Subgraph ([ ]) problem, which is defined as follows. Given a set [ ] of [ ] geometric objects in the plane, we want to compute a maximum-size subset [ ] such that the intersection graph of the objects in [ ] is bipartite. We first give an [ ]-time algorithm that computes an almost optimal solution for the problem on circular-arc graphs. We show that the [ ] problem is [ ]-hard on geometric graphs for which the maximum independent set is [ ]-hard (hence, it is [ ]-hard even on unit squares and unit disks). On the other hand, we give a [ ] for the problem on unit squares and unit disks. Moreover, we show fast approximation algorithms with small-constant factors for the problem on unit squares, unit disks, and unit-height axis parallel rectangles. Additionally, we prove that the Maximum Triangle-free Subgraph ([ ]) problem is NP-hard for axis-parallel rectangles. Here the objective is the same as that of the [ ] except the intersection graph induced by the set [ ] needs to be triangle-free only (instead of being bipartite).
- 1 April 2022
- Published by Elsevier in Computational Geometry
- Vol. 103, 101852
Computing maximum independent set on outerstring graphs and their relatives
- 1 April 2022
- Published by Elsevier in Computational Geometry
- Vol. 103, 101852
Computing maximum independent set on outerstring graphs and their relatives
- 20 October 2021
- Published by Springer Nature
- p. 203-214
Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set
- 20 October 2021
- Published by Springer Nature
- p. 203-214
Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set
- 16 February 2021
- Published by Springer Nature
- p. 234-246
Upward Point Set Embeddings of Paths and Trees
- 16 February 2021
- Published by Springer Nature
- p. 234-246
Upward Point Set Embeddings of Paths and Trees
- 1 June 2020
- Published by Elsevier in Computational Geometry
- Vol. 88, 101610
Packing boundary-anchored rectangles and squares
- 1 June 2020
- Published by Elsevier in Computational Geometry
- Vol. 88, 101610
Packing boundary-anchored rectangles and squares
- 20 July 2016
- Published by Springer Nature
- p. 547-559
Polygon Simplification by Minimizing Convex Corners
- 20 July 2016
- Published by Springer Nature
- p. 547-559
Polygon Simplification by Minimizing Convex Corners
- 1 January 2014
- Published by Springer Nature
- p. 294-305
A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras
- 1 January 2014
- Published by Springer Nature
- p. 294-305
A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras