-
Chapter and Conference Paper
Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set
Consider a vertex-weighted graph G with a source s and a target t. Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from s to t is unique...
-
Chapter and Conference Paper
On the m-eternal Domination Number of Cactus Graphs
Given a graph G, guards are placed on vertices of G. Then vertices are subject to an infinite sequence of attacks so that each attack must be defended by a guard moving from a neighboring vertex. The m-eternal do...
-
Chapter and Conference Paper
Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem
We consider the subgraph isomorphism problem where, given two graphs G (source graph) and F (pattern graph), one is to decide whether there is a (not necessarily induced) subgraph of G isomorphic to F. While man...
-
Chapter and Conference Paper
On Induced Online Ramsey Number of Paths, Cycles, and Trees
An online Ramsey game is a game between Builder and Painter, alternating in turns. They are given a fixed graph H and a an infinite set of independent vertices G. In each round Builder draws a new edge in G and P...
-
Chapter and Conference Paper
A Simple Streaming Bit-Parallel Algorithm for Swap Pattern Matching
The pattern matching problem with swaps is to find all occurrences of a pattern in a text while allowing the pattern to swap adjacent symbols. The goal is to design fast matching algorithm that takes advantage...
-
Chapter and Conference Paper
Automorphisms of the Cube \(n^d\)
Consider a hypergraph \(H_n^d\) where the vertices are points of the d-dimensional combinatorial cube ...
-
Chapter and Conference Paper
On the Tree Search Problem with Non-uniform Costs
Searching in partially ordered structures has been considered in the context of information retrieval and efficient tree-like indices, as well as in hierarchy based knowledge representation. In this paper we f...
-
Article
LP-Based Covering Games with Low Price of Anarchy
We design a new class of vertex and set cover games, where the price of anarchy bounds match the best known constant factor approximation guarantees for the centralized optimization problems for linear and als...
-
Article
On the Geometric Ramsey Number of Outerplanar Graphs
We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth- \(2\) ...
-
Chapter and Conference Paper
WALTZ: A Strong Tzaar-Playing Program
Tzaar is an abstract strategy two-player game, which has recently gained popularity in the gaming community and has won several awards. There are some properties, most notably the high branching factor, that m...
-
Chapter and Conference Paper
Polynomial bounds on geometric Ramsey numbers of ladder graphs
We prove that the geometric Ramsey numbers of the ladder graph on 2n vertices are bounded by O(n 3) and O(n 10), in the convex and general case, respectively. We also prove polynom...
-
Chapter and Conference Paper
LP-Based Covering Games with Low Price of Anarchy
We design a new class of vertex and set cover games, where the price of anarchy bounds match the best known constant factor approximation guarantees for the centralized optimization problems for linear and als...
-
Article
Monochromatic triangles in two-colored plane
We prove that for any partition of the plane into a closed set C and an open set O and for any configuration T of three points, there is a translated and rotated copy of T contained in C or in O.
