19 citations · 30 across the 5 of their papers we have counts for
6 papers
Connectivity with uncertainty regions given as line segments
Sergio Cabello, David Gajser
For a set of points in the plane and a real number , let be the graph defined on by connecting each pair of points at distance at most . We con…
Minimal normal graph covers
David Gajser, Bojan Mohar
A graph is normal if it admits a clique cover and a stable set cover such that each clique in and each stable set in have a vert…
Simple PTAS's for families of graphs excluding a minor
Sergio Cabello, David Gajser
We show that very simple algorithms based on local search are polynomial-time approximation schemes for Maximum Independent Set, Minimum Vertex Cover and Minimum Dominating Set, wh…
The limit of binomial means of a sequence
David Gajser
For a sequence of real numbers and for a parameter , we define the sequence of its arithmetic means and the sequence of its -bin…
Verifying whether One-Tape Non-Deterministic Turing Machines Run in Time
David Gajser
We discuss the following family of problems, parameterized by integers and : Does a given one-tape non-deterministic -state Turing machine make at most …
Verifying Time Complexity of Deterministic Turing Machines
David Gajser
We show that, for all reasonable functions , we can algorithmically verify whether a given one-tape Turing machine runs in time at most . This is a tight bou…