-
Article
A new lower bound for the eternal vertex cover number of graphs
The main result in this paper is a new lower bound to the eternal vertex cover number (evc number) of an arbitrary graph G in terms of the size of the smallest vertex cover in G that includes all the cut vertices...
-
Chapter and Conference Paper
Eternal Vertex Cover on Bipartite Graphs
The Eternal Vertex Cover problem is a dynamic variant of the vertex cover problem. We have a two player game in which guards are placed on some vertices of a graph. In every move, one player (the attacker) attack...
-
Chapter and Conference Paper
An Improvement to Chvátal and Thomassen’s Upper Bound for Oriented Diameter
An orientation of an undirected graph G is an assignment of exactly one direction to each edge of G. The oriented diameter of a graph G is the smallest diameter among all the orientations of G. The maximum orient...
-
Chapter and Conference Paper
A New Lower Bound for the Eternal Vertex Cover Number of Graphs
We obtain a new lower bound for the eternal vertex cover number of an arbitrary graph G, in terms of the cardinality of a vertex cover of minimum size in G containing all its cut vertices. The consequences of the...
-
Chapter and Conference Paper
On Graphs with Minimal Eternal Vertex Cover Number
The eternal vertex cover problem is a variant of the classical vertex cover problem where a set of guards on the vertices have to be dynamically reconfigured from one vertex cover to another in every round of ...
-
Chapter and Conference Paper
A Fix-Point Characterization of Herbrand Equivalence of Expressions in Data Flow Frameworks
Computing Herbrand equivalences of terms in data flow frameworks is well studied in program analysis. While algorithms use iterative fix-point computation on some abstract lattice of expressions relevant to th...
-
Chapter and Conference Paper
Fixed-Orientation Equilateral Triangle Matching of Point Sets
Given a point set P and a class \(\mathcal{C}\) of geometric objects,
-
Chapter and Conference Paper
2-connecting Outerplanar Graphs without Blowing Up the Pathwidth
Given a connected outerplanar graph G with pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O(p). As a consequence, we get a ...
-
Chapter and Conference Paper
Polynomial Time and Parameterized Approximation Algorithms for Boxicity
The boxicity (cubicity) of a graph G, denoted by box(G) (respectively cub(G)), is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (cubes) in ℝ ...
-
Chapter and Conference Paper
A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs
Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional axis parallel boxes in R k . Equivalentl...