A. K. Abu-Affash

activity

20102026

collaborators

9 papers

cs.CG2026

The Minimum Dominating Set Problem on Bipartite Circle Graphs: Complexity and Approximation

A. Karim Abu-Affash, Paz Carmi, Joseph S. B. Mitchell

A circle graph is the intersection graph of a set of chords in a circle. A dominating set of a graph $G = (V, E)$ is a subset $D \subseteq V$ such that every vertex in $V ∖ D$ i…

cs.CG2023

Geometric Spanning Trees Minimizing the Wiener Index

A. Karim Abu-Affash, Paz Carmi, Ori Luwisch +1

The Wiener index of a network, introduced by the chemist Harry Wiener, is the sum of distances between all pairs of nodes in the network. This index, originally used in chemical gr…

cs.CG2023

Dynamic Euclidean Bottleneck Matching

A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi

A fundamental question in computational geometry is for a set of input points in the Euclidean space, that is subject to discrete changes (insertion/deletion of points at each time…

cs.CG2022

Piercing Diametral Disks Induced by Edges of Maximum Spanning Tree

A. Karim Abu-Affash, Paz Carmi, Meytal Maman

Let $P$ be a set of points in the plane and let $T$ be a maximum-weight spanning tree of $P$ . For an edge $(p, q)$ , let $D_{pq}$ be the diametral disk induced by $(p, q)$ , i.e., the…

cs.CG2021

Piercing Pairwise Intersecting Geodesic Disks by Five Points

A. Karim Abu-Affash, Paz Carmi, Meytal Maman

Given a simple polygon $P$ on $n$ vertices, and a set $D$ of $m$ pairwise intersecting geodesic disks in $P$ , we show that five points in $P$ are always sufficient to pierce all th…

cs.DS2020

A Linear-Time Algorithm for Minimum $k$ -Hop Dominating Set of a Cactus Graph

A. Karim Abu-Affash, Paz Carmi, Adi Krasin

Given a graph $G = (V, E)$ and an integer $k \geq 1$ , a $k$ -hop dominating set $D$ of $G$ is a subset of $V$ , such that, for every vertex $v \in V$ , there exists a node $u \in D$ whose…

cs.CG2020

Planar Bichromatic Bottleneck Spanning Trees

A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi +1

Given a set $P$ of $n$ red and blue points in the plane, a \emph{planar bichromatic spanning tree} of $P$ is a spanning tree of $P$ , such that each edge connects between a red and…

cs.CG2013

Approximating the Bottleneck Plane Perfect Matching of a Point Set

A. Karim Abu-Affash, Ahmad Biniaz, Paz Carmi +2

A bottleneck plane perfect matching of a set of $n$ points in $R^{2}$ is defined to be a perfect non-crossing matching that minimizes the length of the longest edge; the len…

cs.CG2010

An Approximation Algorithm for the Euclidean Bottleneck Steiner Tree Problem

A. Karim Abu-Affash

Given two sets of points in the plane, $P$ of $n$ terminals and $S$ of $m$ Steiner points, a Steiner tree of $P$ is a tree spanning all points of $P$ and some (or none or all) poin…