wovepaper — the arXiv observatory

papers

Publications (12)

cs.CC2011

What makes normalized weighted satisfiability tractable

Iyad Kanj, Ge Xia

We consider the weighted antimonotone and the weighted monotone satisfiability problems on normalized circuits of depth at most $t \geq 2$ , abbreviated {\sc wsat $^{-} [t]$ } and {\sc w…

cs.DS2023

Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time

Jianer Chen, Qin Huang, Iyad Kanj +2

We present streaming algorithms for the graph $k$ -matching problem in both the insert-only and dynamic models. Our algorithms, with space complexity matching the best upper bounds,…

cs.CG2023

An $O (3.8 2^{k})$ Time FPT Algorithm for Convex Flip Distance

Haohong Li, Ge Xia

Let $P$ be a convex polygon in the plane, and let $T$ be a triangulation of $P$ . An edge $e$ in $T$ is called a diagonal if it is shared by two triangles in $T$ . A flip of a diagon…

cs.CG2014

There are Plane Spanners of Maximum Degree 4

Nicolas Bonichon, Iyad Kanj, Ljubomir PerkoviÄ +1

Let E be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t >= 1, a spanning subgraph G of E is said to be a t-spanner, or simply a spanner,…

cs.CG2013

The Stretch Factor of the Delaunay Triangulation Is Less Than 1.998

Ge Xia

Let $S$ be a finite set of points in the Euclidean plane. Let $D$ be a Delaunay triangulation of $S$ . The {\em stretch factor} (also known as {\em dilation} or {\em spanning ratio}…

cs.DS2013

Algorithms for Cut Problems on Trees

Iyad Kanj, Guohui Lin, Tian Liu +7

We study the {\sc multicut on trees} and the {\sc generalized multiway Cut on trees} problems. For the {\sc multicut on trees} problem, we present a parameterized algorithm that ru…

cs.CC2017

The Complexity of Tree Partitioning

Zhao An, Qilong Feng, Iyad Kanj +1

Given a tree $T$ on $n$ vertices, and $k, b, s_{1}, \dots, s_{b} \in N$ , the Tree Partitioning problem asks if at most $k$ edges can be removed from $T$ so that the resulting componen…

cs.CG2013

The Yao Graph $Y_{5}$ is a Spanner

Wah Loon Keng, Ge Xia

In this paper we prove that $Y_{5}$ , the Yao graph with five cones, is a spanner with stretch factor $I ¨ = 2 + 3 \approx 3.74$ . Since $Y_{5}$ is the only Yao graph whose status of…

cs.DS2021

Optimal Streaming Algorithms for Graph Matching

Jianer Chen, Qin Huang, Iyad Kanj +1

We present parameterized streaming algorithms for the graph matching problem in both the dynamic and the insert-only models. For the dynamic streaming model, we present a one-pass…

cs.CG2019

New and Improved Spanning Ratios for Yao Graphs

Luis Barba, Prosenjit Bose, Mirela Damian +7

For a set of points in the plane and a fixed integer $k > 0$ , the Yao graph $Y_{k}$ partitions the space around each point into $k$ equiangular cones of angle $I^¸ = 2 I ¨ / k$ , and connect…

cs.DS2016

Computing the flip distance between triangulations

Iyad Kanj, Eric Sedgwick, Ge Xia

Let $T$ be a triangulation of a set $P$ of $n$ points in the plane, and let $e$ be an edge shared by two triangles in $T$ such that the quadrilateral $Q$ forme…

cs.CG2021

Near-Optimal Algorithms for Point-Line Covering Problems