2 citations · 8 across the 13 of their papers we have counts for
9 papers · 1 filter
Above guarantee parameterization for vertex cover on graphs with maximum degree 4
Dekel Tsur
In the vertex cover problem, the input is a graph and an integer , and the goal is to decide whether there is a set of vertices of size at most such that every edge…
An O^*(2.619^k) algorithm for 4-path vertex cover
Dekel Tsur
In the 4-path vertex cover problem, the input is an undirected graph and an integer . The goal is to decide whether there is a set of vertices of size at most such t…
Weighted vertex cover on graphs with maximum degree 3
Dekel Tsur
We give a parameterized algorithm for weighted vertex cover on graphs with maximum degree 3 whose time complexity is , where is the minimum size of a vertex cover…
Parameterized algorithm for 3-path vertex cover
Dekel Tsur
In the 3-path vertex cover problem, the input is an undirected graph and an integer . The goal is to decide whether there is a set of vertices of size at most such t…
The effective entropy of next/previous larger/smaller value queries
Dekel Tsur
We study the problem of storing the minimum number of bits required to answer next/previous larger/smaller value queries on an array of numbers, without storing . We sho…
Dynamic all scores matrices for LCS score
Amir Carmel, Dekel Tsur, Michal Ziv-Ukelson
The problem of aligning two strings A,B in order to determine their similarity is fundamental in the field of pattern matching. An important concept in this domain is the "all scor…