Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a tree t-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t >= 4 and is linearly solvable for t <= 2. The case t = 3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a - b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed. (C) 2010 Elsevier B.V. All rights reserved.

Standard Gibbs' energies of formation of BaCuO2, Y2Cu2O5 and Y2BaCuO5

The Gibbs' energies of formation of BaCuO2, Y2Cu2O5 and Y2BaCuO5 from component oxides have been measured using solid state galvanic cells incorporating CaF2 as the solid electrolyte under pure oxygen at a pressure of 1.01 x 10(5) Pa Because the superconducting compound YBa2Cu3O7-delta coexists with any two of the phases CuO, BaCuO2 and Y2BaCuO5, the data on BaCuO2 and Y2BaCuO5 obtained in this study provide the basis for the evaluation of the Gibbs' energy of formation of the 1-2-3 compound at high temperatures.

Distributed algorithms for edge dominating sets

An edge dominating set for a graph G is a set D of edges such that each edge of G is in D or adjacent to at least one edge in D. This work studies deterministic distributed approximation algorithms for finding minimum-size edge dominating sets. The focus is on anonymous port-numbered networks: there are no unique identifiers, but a node of degree d can refer to its neighbours by integers 1, 2, ..., d. The present work shows that in the port-numbering model, edge dominating sets can be approximated as follows: in d-regular graphs, to within 4 − 6/(d + 1) for an odd d and to within 4 − 2/d for an even d; and in graphs with maximum degree Δ, to within 4 − 2/(Δ − 1) for an odd Δ and to within 4 − 2/Δ for an even Δ. These approximation ratios are tight for all values of d and Δ: there are matching lower bounds.

Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.

Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.

Algorithms for Exact Structure Discovery in Bayesian Networks

Bayesian networks are compact, flexible, and interpretable representations of a joint distribution. When the network structure is unknown but there are observational data at hand, one can try to learn the network structure. This is called structure discovery. This thesis contributes to two areas of structure discovery in Bayesian networks: space--time tradeoffs and learning ancestor relations. The fastest exact algorithms for structure discovery in Bayesian networks are based on dynamic programming and use excessive amounts of space. Motivated by the space usage, several schemes for trading space against time are presented. These schemes are presented in a general setting for a class of computational problems called permutation problems; structure discovery in Bayesian networks is seen as a challenging variant of the permutation problems. The main contribution in the area of the space--time tradeoffs is the partial order approach, in which the standard dynamic programming algorithm is extended to run over partial orders. In particular, a certain family of partial orders called parallel bucket orders is considered. A partial order scheme that provably yields an optimal space--time tradeoff within parallel bucket orders is presented. Also practical issues concerning parallel bucket orders are discussed. Learning ancestor relations, that is, directed paths between nodes, is motivated by the need for robust summaries of the network structures when there are unobserved nodes at work. Ancestor relations are nonmodular features and hence learning them is more difficult than modular features. A dynamic programming algorithm is presented for computing posterior probabilities of ancestor relations exactly. Empirical tests suggest that ancestor relations can be learned from observational data almost as accurately as arcs even in the presence of unobserved nodes.

Phase Relations in the System Cu-Gd-O and Gibbs Energy of Formation of CuGd204

The phase relations in the system Cu-Gd-O have been determined at 1273 K by X-ray diffrac- tion, optical microscopy, and electron microprobe analysis of samples equilibrated in quartz ampules and in pure oxygen. Only one ternary compound, CuGd2O4, was found to be stable. The Gibbs free energy of formation of this compound has been measured using the solid-state cell Pt, Cu2O + CuGd2O4 + Gd2O3 // (Y2O3) ZrO2 // CuO + Cu2O, Pt in the temperature range of 900 to 1350 K. For the formation of CuGd2O4 from its binary component oxides, CuO (s) + Gd2O3 (s) → CuGd2O4 (s) ΔG° = 8230 - 11.2T (±50) J mol-1 Since the formation is endothermic, CuGd2O4 becomes thermodynamically unstable with respect to CuO and Gd2O3 below 735 K. When the oxygen partial pressure over CuGd2O4 is lowered, it decomposes according to the reaction 4CuGd2O4 (s) → 4Gd2O3 (s) + 2Cu2O (s) + O2 (g) for which the equilibrium oxygen potential is given by Δμo 2 = −227,970 + 143.2T (±500) J mol−1 An oxygen potential diagram for the system Cu-Gd-O at 1273 K is presented.

Phase relations in the systems Cu–O–R2O3(R = Tm, Lu) and Gibbs energies of formation of Cu2R2O5 compounds

The phase relations in the systems Cu–O–R2O3(R = Tm, Lu) have been determined at 1273 K by X-ray diffraction, optical microscopy and electron probe microanalysis of samples equilibrated in evacuated quartz ampules and in pure oxygen. Only ternary compounds of the type Cu2R2O5 were found to be stable. The standard Gibbs energies of formation of the compounds have been measured using solid-state galvanic cells of the type, Pt|Cu2O + Cu2R2O5+ R2O3‖(Y2O3)ZrO2‖CuO + Cu2O‖Pt in the temperature range 950–1325 K. The standard Gibbs energy changes associated with the formation of Cu2R2O5 compounds from their binary component oxides are: 2CuO(s)+ Tm2O3(s)→Cu2Tm2O5(s), ΔG°=(10400 – 14.0 T/K)± 100 J mol–1, 2CuO(s)+ Lu2O3(s)→Cu2Lu2O5(s), ΔG°=(10210 – 14.4 T/K)± 100 J mol–1 Since the formation is endothermic, the compounds become thermodynamically unstable with respect to component oxides at low temperatures, Cu2Tm2O5 below 743 K and Cu2Lu2O5 below 709 K. When the chemical potential of oxygen over the Cu2R2O5 compounds is lowered, they decompose according to the reaction, 2Cu2R2O5(s)→2R2O3(s)+ 2Cu2O(s)+ O2(g) The equilibrium oxygen potential corresponding to this reaction is obtained from the emf. Oxygen potential diagrams for the Cu–O–R2O3 systems at 1273 K are presented.

Algorithms for Routing and Centralized Scheduling in IEEE 802.16 Mesh Networks

IEEE 802.16 standards for Wireless Metropolitan Area Networks (WMANs) include a mesh mode of operation for improving the coverage and throughput of the network. In this paper, we consider the problem of routing and centralized scheduling for such networks. We first fix the routing, which reduces the network to a tree. We then present a finite horizon dynamic programming framework. Using it we obtain various scheduling algorithms depending upon the cost function. Next we consider simpler suboptimal algorithms and compare their performances.

New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Load balancing algorithms for an extended hypercube

Reduction of the execution time of a job through equitable distribution of work load among the processors in a distributed system is the goal of load balancing. Performance of static and dynamic load balancing algorithms for the extended hypercube, is discussed. Threshold algorithms are very well-known algorithms for dynamic load balancing in distributed systems. An extension of the threshold algorithm, called the multilevel threshold algorithm, has been proposed. The hierarchical interconnection network of the extended hypercube is suitable for implementing the proposed algorithm. The new algorithm has been implemented on a transputer-based system and the performance of the algorithm for an extended hypercube is compared with those for mesh and binary hypercube networks

Absolutely expedient algorithms for learning Nash equilibria

This paper considers a multi-person discrete game with random payoffs. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A class of absolutely expedient learning algorithms for the game based on a decentralised team of Learning Automata is presented. These algorithms correspond, in some sense, to rational behaviour on the part of the players. All stable stationary points of the algorithm are shown to be Nash equilibria for the game. It is also shown that under some additional constraints on the game, the team will always converge to a Nash equilibrium.