Paired-domination in inflated graphs

The inflation G_I of a graph G with n(G) vertices and m(G) edges is obtained from G by replacing every vertex of degree d of G by a clique K_d. A set S of vertices in a graph G is a paired dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired domination number γ_p(G) is the minimum cardinality of a paired dominating set of G. In this paper, we show that if a graph G has a minimum degree δ(G)2, then n(G)γ_p(G_I)4m(G)/[δ(G)+1], and the equality γ_p(G_I) = n(G) holds if and only if G has a perfect matching. In addition, we present a linear time algorithm to compute a minimum paired-dominating set for an inflation tree.     

Resolvability and the upper dimension of graphs

For an ordered set W = {w₁, w₂,…, w_k} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r(v | W) = (d(v, w₁), d(v, w₂),…, d(v, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented.

A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim⁺(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim⁺(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim⁺(G) = res(G) = n − 1 if and only if G = K_n, while dim⁺(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle.

The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim⁺(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim⁺(G) ≥ N and dim⁺(G) − dim(G) ≥ N.     

On Stieltjes functions and Hankel operators

Let G be a Stieltjes function which is analytic in the open right half plane. It is shown that G is in H^∞(RHP) if and only if the Hankel operator H_G on H²(RHP) with symbol G is nuclear. If G is in H^∞(RHP) it is shown that the non-tangential limit of G at s = 0 equals twice the nuclear norm of H_G.     

Greedy algorithms, H-colourings and a complexity-theoretic dichotomy

Let H be a fixed undirected graph. An H-colouring of an undirected graph G is a homomorphism from G to H. If the vertices of G are partially ordered then there is a generic non-deterministic greedy algorithm which computes all lexicographically first maximal H-colourable subgraphs of G. We show that the complexity of deciding whether a given vertex of G is in a lexicographically first maximal H-colourable subgraph of G is NP-complete, if H is bipartite, and Σ₂^p-complete, if H is non-bipartite. This result complements Hell and Ne et il's seminal dichotomy result that the standard H-colouring problem is in P, if H is bipartite, and NP-complete, if H is non-bipartite. Our proofs use the basic techniques established by Hell and Ne et il, combinatorially adapted to our scenario.     

Uniform controllable sets of left-invariant vector fields on compact Lie groups

A set of vector fields on a differentiable manifold M is said to be uniformly completely controllable (u.c.c.) if there exists a nonnegative integer N such that evert pair (p, q) of point of M can be joined by a trajectory, or positive orbit, of which involves at most N switches.

In this article we show that if M is a Lie group G and a set of left-invariant vector fields on G, N must be greater than or equal to dim(G)-1. We also construct sets of vector fields which are uniformly completely controllable in dim(G)-1 switches when G is the Lie group of any compact real form of g and g runs over all classical simple Lie algebras over .     

Guarding galleries and terrains

Let P be a polygon with n vertices. We say that two points of P see each other if the line segment connecting them lies inside (the closure of) P. In this paper we present efficient approximation algorithms for finding the smallest set G of points of P so that each point of P is seen by at least one point of G, and the points of G are constrained to be belong to the set of vertices of an arbitrarily dense grind. We also present similar algorithms for terrains and polygons with holes.     

Algorithms for generalized vertex-rankings of partial k-trees

A c-vertex-ranking of a graph G for a positive integer c is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels >i leaves connected components, each having at most c vertices with label i. A c-vertex-ranking is optimal if the number of labels used is as small as possible. We present sequential and parallel algorithms to find an optimal c-vertex-ranking of a partial k-tree, that is, a graph of treewidth bounded by a fixed integer k. The sequential algorithm takes polynomial-time for any positive integer c. The parallel algorithm takes O(log n) parallel time using a polynomial number of processors on the common CRCW PRAM, where n is the number of vertices in G.     

Tree spanners on chordal graphs: complexity and algorithms

A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The T t-S problem asks whether a graph admits a tree t-spanner, given t. We substantially strengthen the hardness result of Cai and Corneil (SIAM J. Discrete Math. 8 (1995) 359–387) by showing that, for any t4, T t-S is NP-complete even on chordal graphs of diameter at most t+1 (if t is even), respectively, at most t+2 (if t is odd). Then we point out that every chordal graph of diameter at most t−1 (respectively, t−2) admits a tree t-spanner whenever t2 is even (respectively, t3 is odd), and such a tree spanner can be constructed in linear time.

The complexity status of T 3-S still remains open for chordal graphs, even on the subclass of undirected path graphs that are strongly chordal as well. For other important subclasses of chordal graphs, such as very strongly chordal graphs (containing all interval graphs), 1-split graphs (containing all split graphs) and chordal graphs of diameter at most 2, we are able to decide T 3-S efficiently.     

Computing planar swept polygons under translation

A translational sweep is the translating of a polygon, called the generatrix G, around another polygon, called the directrix D, under two conditions: (1) G is always in contact with D; and (2) the interiors of G and D do not intersect. Three classes of translational sweep are studied, including the case in which both G and D are convex; the case in which G is convex, D monotone; and the case in which both are monotone. Efficient algorithms for computing the trajectory and the swept area as well as geometric and computational properties are presented for each class. A notion called the inverse generatrix, which reveals a duality between the trajectory and the swept polygon, is introduced to reduce complexity.     

Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard

Let G=(V,E) be an undirected graph and C a subset of vertices. If the sets B_r(v)∩C, vV (respectively, vVC), are all nonempty and different, where B_r(v) denotes the set of all points within distance r from v, we call C an r-identifying code (respectively, an r-locating-dominating code). We prove that, given a graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r.     

On structuring proof search for first order linear logic

Full first-order linear logic can be presented as an abstract logic programming language in Miller's system Forum, which yields a sensible operational interpretation in the ‘proof search as computation’ paradigm. However, Forum still has to deal with syntactic details that would normally be ignored by a reasonable operational semantics. In this respect, Forum improves on Gentzen systems for linear logic by restricting the language and the form of inference rules. We further improve on Forum by restricting the class of formulae allowed, in a system we call G-Forum, which is still equivalent to full first-order linear logic. The only formulae allowed in G-Forum have the same shape as Forum sequents: the restriction does not diminish expressiveness and makes G-Forum amenable to proof theoretic analysis. G-Forum consists of two (big) inference rules, for which we show a cut elimination procedure. This does not need to appeal to finer detail in formulae and sequents than is provided by G-Forum, thus successfully testing the internal symmetries of our system.     

On extended P4-reducible and extended P4-sparse graphs

A graph G was defined in [16] as P₄-reducible, if no vertex in G belongs to more than one chordless path on four vertices or P₄. A graph G is defined in [15] as P₄-sparse if no set of five vertices induces more than one P₄, in G. P₄-sparse graphs generalize both P₄-reducible and the well known class of p₄-free graphs or cographs. In an extended abstract in [11] the first author introduced a method using the modular decomposition tree of a graph as the framework for the resolution of algorithmic problems. This method was applied to the study of P₄-sparse and extended P₄-sparse graphs.

In this paper, we begin by presenting the complete information about the method used in [11]. We propose a unique tree representation of P₄-sparse and a unique tree representation of P₄-reducible graphs leading to a simple linear recognition algorithm for both classes of graphs. In this way we simplify and unify the solutions for these problems, presented in [16–19]. The tree representation of an n-vertex P₄-sparse or a P₄-reducible graph is the key for obtaining O(n) time algorithms for the weighted version of classical optimization problems solved in [20]. These problems are NP-complete on general graphs.

Finally, by relaxing the restriction concerning the exclusion of the C₅ cycles from P₄-sparse and P₄-reducible graphs, we introduce the class of the extended P4-sparse and the class of the extendedP₄-reducible graphs. We then show that a minimal amount of additional work suffices for extending most of our algorithms to these new classes of graphs.     

t-Spanners for metric space searching

The problem of Proximity Searching in Metric Spaces consists in finding the elements of a set which are close to a given query under some similarity criterion. In this paper we present a new methodology to solve this problem, which uses a t-spanner G′(V, E) as the representation of the metric database. A t-spanner is a subgraph G′(V, E) of a graph G(V, A), such that E  A and G′ approximates the shortest path costs over G within a precision factor t.

Our key idea is to regard the t-spanner as an approximation to the complete graph of distances among the objects, and to use it as a compact device to simulate the large matrix of distances required by successful search algorithms such as AESA. The t-spanner properties imply that we can use shortest paths over G′ to estimate any distance with bounded-error factor t.

For this sake, several t-spanner construction, updating, and search algorithms are proposed and experimentally evaluated. We show that our technique is competitive against current approaches. For example, in a metric space of documents our search time is only 9% over AESA, yet we need just 4% of its space requirement. Similar results are obtained in other metric spaces.

Finally, we conjecture that the essential metric space property to obtain good t-spanner performance is the existence of clusters of elements, and enough empirical evidence is given to support this claim. This property holds in most real-world metric spaces, so we expect that t-spanners will display good behavior in most practical applications. Furthermore, we show that t-spanners have a great potential for improvements.     

Hankel norm approximation for well-posed linear systems

The sub-optimal Hankel norm approximation problem is solved for a well-posed linear system with generating operators (A,B,C) and transfer function G satisfying some mild assumptions. In the special case of the sub-optimal Nehari problem, an explicit parameterization of all solutions is obtained in terms of the system parameters A, B, C and G(0).     

Efficient algorithms for shortest distance queries on special classes of polygons

The problem of finding a rectilinear minimum bend path (RMBP) between two designated points inside a rectilinear polygon has applications in robotics and motion planning. In this paper, we present efficient algorithms to solve the query version of the RMBP problem for special classes of rectilinear polygons given their visibility graphs. Specifically, we show that given an unweighted graph G = (V, E), with ¦V¦ = N and ¦E¦ = M, algorithms to preprocess G in linear space and time such that the shortest distance queries — queries asking for the distance between any pair of nodes in the graph — can be answered in constant time and space are presented in this paper. For the case of a chordal graph G, our algorithms give a distance which is at most one away from the actual shortest distance. When G is a K-chordal graph, our algorithm produces an exact shortest distance in O(K) time. We also present a non-trivial parallel implementation of the sequential preprocessing algorithm for the CREW-PRAM model which runs in O(log² N) time using O(N + M) processors. After the preprocessing, we can answer the queries in constant time using a single processor.     

Algorithms of discretization of algebraic spatial curves on homogeneous cubical grids

In this paper new methods of discretization (integer approximation) of algebraic spatial curves in the form of intersecting surfaces P(x, y, z) = 0 and Q(x, y, z) = 0 are analyzed.

The use of homogeneous cubical grids G(h³) to discretize a curve is the essence of the method. Two new algorithms of discretization (on 6-connected grid G_6c(h³) and 26-connected grid G₂₆(h³)) are presented based on the method above. Implementation of the algorithms for algebraic spatial curves is suggested. The elaborated algorithms are adjusted for application in computer graphics and numerical control of machine tools.     

Stability of nonlinear time-varying feedback systems

In this paper, the stability of nonlinear time-varying feedback systems is studied using a “passive operator” technique. The feedback system is assumed to consist of a linear time-invariant operator G(s) in the forward path and a nonlinear time-varying gain function f(·)K(t) in the feedback path. The stability condition indicates that the bound on the time derivative [dK(t)/(dt)] depends both on the nonlinearity f(·) and the multiplier Z(s) chosen to make G(s)Z(s) positive real. It is also shown that the main result in this paper can be specialized to yield many of the results obtained so far for nonlinear time-invariant systems and linear time-varying systems.     

Mach band optical ray illusion—Drawing with the second differential

Mach bands running along convex ramp edges in a computer graphics image produce the illusion of optical rays, and a concave ramp edge defines an interface for “reflection.” The positive and negative brightness enhancements (E) observed in the illusion are simulated by convolving the pattern of gradient increments (Δg) computed at the edges with a Gaussian kernel (G): E ∝ − Δg G.     

A limit characterization for the number of spanning trees of graphs

In this paper we propose a limit characterization of the behaviour of classes of graphs with respect to their number of spanning trees. Let {G_n} be a sequence of graphs G₀,G₁,G₂,… that belong to a particular class. We consider graphs of the form K_n−G_n that result from the complete graph K_n after removing a set of edges that span G_n. We study the spanning tree behaviour of the sequence {K_n−G_n} when n→∞ and the number of edges of G_n scales according to n. More specifically, we define the spanning tree indicator ({G_n}), a quantity that characterizes the spanning tree behaviour of {K_n−G_n}. We derive closed formulas for the spanning tree indicators for certain well-known classes of graphs. Finally, we demonstrate that the indicator can be used to compare the spanning tree behaviour of different classes of graphs (even when their members never happen to have the same number of edges).