Distance and routing labeling schemes for non-positively curved plane graphs

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently (e.g., in constant or logarithmic time) by merely inspecting the labels of u and v, without using any other information. Similarly, routing labeling schemes are schemes that label the vertices of a graph with short labels in such a way that given the label of a source vertex and the label of a destination, it is possible to compute efficiently (e.g., in constant or logarithmic time) the port number of the edge from the source that heads in the direction of the destination. In this paper we show that the three major classes of non-positively curved plane graphs enjoy such distance and routing labeling schemes using O(log²n) bit labels on n-vertex graphs. In constructing these labeling schemes interesting metric properties of those graphs are employed.     

Proximity‐preserving labeling schemes

This article considers informative labeling schemes for graphs. Specifically, the question introduced is whether it is possible to label the vertices of a graph with short labels in such a way that the distance between any two vertices can be inferred from inspecting their labels. A labeling scheme enjoying this property is termed a proximity‐preserving labeling scheme. It is shown that, for the class of n‐vertex weighted trees with M‐bit edge weights, there exists such a proximity‐preserving labeling scheme using O(M log n + log²n) bit labels. For the family of all n‐vertex unweighted graphs, a labeling scheme is proposed that using O(log² n · κ · n^1/κ) bit labels can provide approximate estimates to the distance, which are accurate up to a factor of In particular, using O(log³n) bit labels, the scheme can provide estimates accurate up to a factor of $\sqrt{2 \log n}$. (For weighted graphs, one of the log n factors in the label size is replaced by a factor logarithmic in the network's diameter.) © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 167–176, 2000     

Cohen–Macaulay Isolated Singularities with a Dualizing Module

We generalize results of Foxby concerning a commutative Nötherian ring to a certain noncommutative Nötherian algebra Λ over a commutative Gorenstein complete local ring. We assume that Λ is a Cohen–Macaulay isolated singularity having a dualizing module. Then the same method as in the commutative cases works and we obtain a category equivalence between two subcategories of mod Λ, one of which includes all finitely generated modules of finite Gorenstein dimension. We give examples of such algebras which are not Gorenstien; orders related to almost Bass orders and some k-Gorenstein algebras for an integer k.Presented by I. Reiten ^★The author is supported by Grant-in-Aid for Scientific Researches B(1) No. 14340007 in Japan.     

Geometric minimality conditions for systems of exponentials inL p [−π, π]

A proof is given of the stability theorem for minimal systems of exponentialse(Λ) = {e ^iλx }λ∈Λ inL _p [−π, π], where Λ ⊂ ℂ is a discrete subset. Geometric minimality conditions for such systems are obtained. Translated fromMatematicheskie Zametki, Vol. 58, No. 5, pp. 773–777, November, 1995. I wish to express gratitude to A. A. Shkalikov, who posed the problem and paid constant attention to this work.     

The Category of Lattices over a Lattice-Finite Ring

It is well-known that for a lattice-finite order Λ over a complete discrete valuation domain, the radical of Λ-lat (the category of Λ-lattices) is nilpotent modulo projectives. Iyama has shown that this property merely depends on the combinatorial data given by the Auslander–Reiten quiver of Λ. Moreover, he established a criterion for a finite (symmetrizable) translation quiver Q to be the Auslander–Reiten quivers of an order Λ. We improve his characterization by showing that the remaining conditions on Q can be replaced by the existence of an additive function on the vertices of Q (Theorem 4). Our proof rests on a functorial theory of ladders, expressing the Auslander–Reiten structure of Λ-lat by means of an adjoint pair of functors L⊣L⁻ in the homotopy category of two-termed complexes over Λ-lat. Presented by I. Reiten Mathematics Subject Classifications (2000) Primary: 16G70, 16G30; secondary: 16G60.     

Anisotropic branching random walks on homogeneous trees

Symmetric branching random walk on a homogeneous tree exhibits a weak survival phase: For parameter values in a certain interval, the population survives forever with positive probability, but, with probability one, eventually vacates every finite subset of the tree. In this phase, particle trails must converge to the geometric boundaryΩ of the tree. The random subset Λ of the boundary consisting of all ends of the tree in which the population survives, called the limit set of the process, is shown to have Hausdorff dimension no larger than one half the Hausdorff dimension of the entire geometric boundary. Moreover, there is strict inequality at the phase separation point between weak and strong survival except when the branching random walk is isotropic. It is further shown that in all cases there is a distinguished probability measure μ supported by Ω such that the Hausdorff dimension of Λ∩Ω_μ, where Ω_μ is the set of μ-generic points of Ω, converges to one half the Hausdorff dimension of Ω_μ at the phase separation point. Exact formulas are obtained for the Hausdorff dimensions of Λ and Λ∩Ω_μ, and it is shown that the log Hausdorff dimension of Λ has critical exponent 1/2 at the phase separation point. Received: 30 June 1998 / Revised version: 10 March 1999     

Dilations and Completions for Gabor Systems

Let be a full rank time-frequency lattice in ℝ ^d ×ℝ ^d . In this note we first prove that any dual Gabor frame pair for a Λ-shift invariant subspace M can be dilated to a dual Gabor frame pair for the whole space L ²(ℝ ^d ) when the volume v(Λ) of the lattice Λ satisfies the condition v(Λ)≤1, and to a dual Gabor Riesz basis pair for a Λ-shift invariant subspace containing M when v(Λ)>1. This generalizes the dilation result in Gabardo and Han (J. Fourier Anal. Appl. 7:419–433, [2001]) to both higher dimensions and dual subspace Gabor frame pairs. Secondly, for any fixed positive integer N, we investigate the problem whether any Bessel–Gabor family G(g,Λ) can be completed to a tight Gabor (multi-)frame G(g,Λ)∪(∪ _j=1 ^N G(g _j ,Λ)) for L ²(ℝ ^d ). We show that this is true whenever v(Λ)≤N. In particular, when v(Λ)≤1, any Bessel–Gabor system is a subset of a tight Gabor frame G(g,Λ)∪G(h,Λ) for L ²(ℝ ^d ). Related results for affine systems are also discussed. Communicated by Chris Heil.     

Analytic functions over a field of power series

 We extend the notion of absolute convergence for real series in several variables to a notion of convergence for series in a power series field ℝ((t ^Γ)) with coefficients in ℝ. Subsequently, we define a natural notion of analytic function at a point of ℝ((t ^Γ))^m. Then, given a real function f analytic on a open box I of ℝ ^m , we extend f to a function f ^★ which is analytic on a subset of ℝ((t ^Γ)) ^m containing I. We prove that the functions f ^★ share with real analytic functions certain basic properties: they are , they have usual Taylor development, they satisfy the inverse function theorem and the implicit function theorem. Received: 5 October 2000 / Revised version: 19 June 2001 / Published online: 12 July 2002     

Maximum stable set formulations and heuristics based on continuous optimization

 The stability number α(G) for a given graph G is the size of a maximum stable set in G. The Lovász theta number provides an upper bound on α(G) and can be computed in polynomial time as the optimal value of the Lovász semidefinite program. In this paper, we show that restricting the matrix variable in the Lovász semidefinite program to be rank-one and rank-two, respectively, yields a pair of continuous, nonlinear optimization problems each having the global optimal value α(G). We propose heuristics for obtaining large stable sets in G based on these new formulations and present computational results indicating the effectiveness of the heuristics. Received: December 13, 2000 / Accepted: September 3, 2002 Published online: December 19, 2002 RID="★" ID="★" Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. Key Words. maximum stable set – maximum clique – minimum vertex cover – semidefinite program – semidefinite relaxation – continuous optimization heuristics – nonlinear programming Mathematics Subject Classification (2000): 90C06, 90C27, 90C30     

On anti-magic labeling for graph products

An anti-magic labeling of a finite simple undirected graph with p vertices and q edges is a bijection from the set of edges to the set of integers {1,2,…,q} such that the vertex sums are pairwise distinct, where the vertex sum at one vertex is the sum of labels of all edges incident to such vertex. A graph is called anti-magic if it admits an anti-magic labeling. Hartsfield and Ringel conjectured in 1990 that all connected graphs except K₂ are anti-magic. Recently, Alon et al. showed that this conjecture is true for dense graphs, i.e. it is true for p-vertex graphs with minimum degree Ω(logp). In this article, new classes of sparse anti-magic graphs are constructed through Cartesian products and lexicographic products.     

The merchant subtour problem

 We consider the problem of a travelling merchant who makes money by buying commodities where they are cheap and selling them in other places where he can make a profit. The merchant ships commodities of his own choice in a van of fixed capacity. Given the prices of all the commodities in all of the places, and the cost of driving from one place to another, the problem the merchant faces each day is to select a subset of the cities that he can visit in a day, and to determine the order in which the cities are visited, such that the total profit is maximised. We call this problem the Merchant Subtour Problem. The MSP models the pricing problem of a rather complex pickup and delivery problem that was given to us by the Dutch logistics company Van Gend & Loos. We show that a special case of the MSP has a totally unimodular constraint matrix. This knowledge enables us to develop a tabu-search algorithm for finding good feasible solutions to the MSP, and a branch-and-price-and-cut algorithm for solving the MSP to optimality. The relaxations solved in each node of the branch-and-bound tree are strengthened by lifted knapsack inequalities, lifted cycle inequalities and mod-k cuts. We present computational results on data sets derived from our main instance of the Van Gend & Loos pickup and delivery problem. Received: October 25, 2000 / Accepted: January 23, 2002 Published online: September 27, 2002 RID="★" ID="★" This research was partially supported by EC – Fifth Framework Programme contract IST-1999-14186 (Project ALCOM-FT: Algorithms and Complexity – Future Technologies).     

Graph partitioning using linear and semidefinite programming

 Graph partition is used in the telecommunication industry to subdivide a transmission network into small clusters. We consider both linear and semidefinite relaxations for the equipartition problem and present numerical results on real data from France Telecom networks with up 900 nodes, and also on randomly generated problems. Received: August 8, 2001 / Accepted: November 9, 2001 Published online: December 9, 2002 RID="★★" ID="★★" This research was carried out while this author was working at France Telecom R & D, 38–40 rue du Général Leclerc, F-92794 Issy-Les-Moulineaux Cedex 9, France. RID="★" ID="★" This author greatfully acknowledges financial support from the Austrian Science Foundation FWF Project P12660-MAT. Key words. graph partitioning – semidefinite programming     

Dynamic knapsack sets and capacitated lot-sizing

 A dynamic knapsack set is a natural generalization of the 0-1 knapsack set with a continuous variable studied recently. For dynamic knapsack sets a large family of facet-defining inequalities, called dynamic knapsack inequalities, are derived by fixing variables to one and then lifting. Surprisingly such inequalities have the simultaneous lifting property, and for small instances provide a significant proportion of all the facet-defining inequalities. We then consider single-item capacitated lot-sizing problems, and propose the joint study of three related sets. The first models the discrete lot-sizing problem, the second the continuous lot-sizing problem with Wagner-Whitin costs, and the third the continuous lot-sizing problem with arbitrary costs. The first set that arises is precisely a dynamic knapsack set, the second an intersection of dynamic knapsack sets, and the unrestricted problem can be viewed as both a relaxation and a restriction of the second. It follows that the dynamic knapsack inequalities and their generalizations provide strong valid inequalities for all three sets. Some limited computation results are reported as an initial test of the effectiveness of these inequalities on capacitated lot-sizing problems. Received: March 28, 2001 / Accepted: November 9, 2001 Published online: September 27, 2002 RID="★" ID="★" Research carried out with financial support of the project TMR-DONET nr. ERB FMRX–CT98–0202 of the European Union. Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium. Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium. Key words. knapsack sets – valid inequalities – simultaneous lifting – lot-sizing – Wagner-Whitin costs     

The structure on invariant measures of <Emphasis Type="Italic">C</Emphasis><Superscript>1</Superscript> generic diffeomorphisms

Let Λ be an isolated non-trivial transitive set of a C 1 generic diffeomorphism f ∈ Diff (M ). We show that the space of invariant measures supported on Λ coincides with the space of accumulation measures of time averages on one orbit. Moreover, the set of points having this property is residual in Λ (which implies that the set of irregular+ points is also residual in Λ). As an application, we show that the non-uniform hyperbolicity of irregular+ points in Λ with totally 0 measure (resp., the non-uniform hyperbolicity of a generic subset in Λ) determines the uniform hyperbolicity of Λ.     

Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005     

Combinatorial Integer Labeling Theorems on Finite Sets with Applications

Tucker’s well-known combinatorial lemma states that, for any given symmetric triangulation of the n-dimensional unit cube and for any integer labeling that assigns to each vertex of the triangulation a label from the set {±1,±2,…,±n} with the property that antipodal vertices on the boundary of the cube are assigned opposite labels, the triangulation admits a 1-dimensional simplex whose two vertices have opposite labels. In this paper, we are concerned with an arbitrary finite set D of integral vectors in the n-dimensional Euclidean space and an integer labeling that assigns to each element of D a label from the set {±1,±2,…,±n}. Using a constructive approach, we prove two combinatorial theorems of Tucker type. The theorems state that, under some mild conditions, there exists two integral vectors in D having opposite labels and being cell-connected in the sense that both belong to the set {0,1} ⁿ +q for some integral vector q. These theorems are used to show in a constructive way the existence of an integral solution to a system of nonlinear equations under certain natural conditions. An economic application is provided.     

Memetic algorithm for the antibandwidth maximization problem

The antibandwidth maximization problem (AMP) consists of labeling the vertices of a n-vertex graph G with distinct integers from 1 to n such that the minimum difference of labels of adjacent vertices is maximized. This problem can be formulated as a dual problem to the well known bandwidth problem. Exact results have been proved for some standard graphs like paths, cycles, 2 and 3-dimensional meshes, tori, some special trees etc., however, no algorithm has been proposed for the general graphs. In this paper, we propose a memetic algorithm for the antibandwidth maximization problem, wherein we explore various breadth first search generated level structures of a graph—an imperative feature of our algorithm. We design a new heuristic which exploits these level structures to label the vertices of the graph. The algorithm is able to achieve the exact antibandwidth for the standard graphs as mentioned. Moreover, we conjecture the antibandwidth of some 3-dimensional meshes and complement of power graphs, supported by our experimental results.     

N/V-limit for stochastic dynamics in continuous particle systems

We provide an N/V-limit for the infinite particle, infinite volume stochastic dynamics associated with Gibbs states in continuous particle systems on ℝ ^d ,d≥1. Starting point is an N-particle stochastic dynamic with singular interaction and reflecting boundary condition in a subset Λ⊂ℝ ^d with finite volume (Lebesgue measure) V=|Λ|<∞. The aim is to approximate the infinite particle, infinite volume stochastic dynamic by the above N-particle dynamic in Λ as N→∞ and V→∞ such that N/V→ρ, where ρ is the particle density. First we derive an improved Ruelle bound for the canonical correlation functions under an appropriate relation between N and V. Then tightness is shown by using the Lyons–Zheng decomposition. The equilibrium measures of the accumulation points are identified as infinite volume canonical Gibbs measures by an integration by parts formula and the accumulation points themselves are identified as infinite particle, infinite volume stochastic dynamics via the associated martingale problem. Assuming a property closely related to Markov uniqueness and weaker than essential self-adjointness, via Mosco convergence techniques we can identify the accumulation points as Markov processes and show uniqueness. I.e., all accumulation corresponding to one invariant canonical Gibbs measure coincide. The proofs work for general repulsive interaction potentials ϕ of Ruelle type and all temperatures, densities, and dimensions d≥1, respectively. ϕ may have a nontrivial negative part and infinite range as e.g. the Lennard–Jones potential. Additionally, our result provides as a by-product an approximation of grand canonical Gibbs measures by finite volume canonical Gibbs measures with empty boundary condition.     

Simplicity of <Emphasis Type="Italic">C</Emphasis>*-algebras associated to row-finite locally convex higher-rank graphs

In a previous work, the authors showed that the C*-algebra C*(Λ) of a row-finite higher-rank graph Λ with no sources is simple if and only if Λ is both cofinal and aperiodic. In this paper, we generalise this result to row-finite higher-rank graphs which are locally convex (but may contain sources). Our main tool is Farthing’s “removing sources” construction which embeds a row-finite locally convex higher-rank graph in a row-finite higher-rank graph with no sources in such a way that the associated C*-algebras are Morita equivalent.     

Maxwell equations and the direction of the electromagnetic field

Let M₀ be the Minkowski space, let Λ₂(M₀) be the space of bivectors in M₀, and let G¹ ⊂ Λ₂(M₀) be the manifold of directions of the physical space, consisting of simple bivectors with square −1. A mapping F: U → Λ₂(M₀), U ⊂ ℝ⁴, satisfying the Maxwell equations is regarded as the tensor of an electromagnetic field in vacuum. The field is described on the basis of a special decomposition F = eω + h(*ω), where the mapping ω: U → G¹ is called the direction of the field, and e: U → (0, +∞) and h: U → ℝ are the electric and magnetic coefficients of the field. The Maxwell equations are reformulated in terms of ω, e, and h. Electromagnetic fields whose set of directions is a point or a one-dimensional subset of G¹ are considered. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 329, 2005, pp. 118–146.