7 Result(s)
-
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
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...
