Structural similarity of directed universal hierarchical graphs: A low computational complexity approach

In the present paper we mainly introduce an efficient approach to measure the structural similarity of so called directed universal hierarchical graphs. We want to underline that directed universal hierarchical graphs can be obtained from generalized trees which are already introduced. In order to classify these graphs, we state our novel graph similarity method. As a main result we notice that our novel algorithm has low computational complexity. (c) 2007 Elsevier Inc. All rights reserved.

Information theoretic measures of UHG graphs with low computational complexity

We introduce a novel graph class we call universal hierarchical graphs (UHG) whose topology can be found numerously in problems representing, e.g., temporal, spacial or general process structures of systems. For this graph class we show, that we can naturally assign two probability distributions, for nodes and for edges, which lead us directly to the definition of the entropy and joint entropy and, hence, mutual information establishing an information theory for this graph class. Furthermore, we provide some results under which conditions these constraint probability distributions maximize the corresponding entropy. Also, we demonstrate that these entropic measures can be computed efficiently which is a prerequisite for every large scale practical application and show some numerical examples. (c) 2007 Elsevier Inc. All rights reserved.

On the Complexity of Universal Leader Election

Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This paper focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most "obvious" complexity bounds have not been proven for randomized algorithms. The "obvious" lower bounds of O(m) messages (m is the number of edges in the network) and O(D) time (D is the network diameter) are non-trivial to show for randomized (Monte Carlo) algorithms. (Recent results that show that even O(n) (n is the number of nodes in the network) is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms (except for the limited case of comparison algorithms, where it was also required that some nodes may not wake up spontaneously, and that D and n were not known).

We establish these fundamental lower bounds in this paper for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (such algorithms should work for all graphs), apply to every D, m, and n, and hold even if D, m, and n are known, all the nodes wake up simultaneously, and the algorithms can make anyuse of node's identities. To show that these bounds are tight, we present an O(m) messages algorithm. An O(D) time algorithm is known. A slight adaptation of our lower bound technique gives rise to an O(m) message lower bound for randomized broadcast algorithms.

An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. (The answer is known to be negative in the deterministic setting). We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that trade-off messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.

On the Complexity of Universal Leader Election

Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This article focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most "obvious" complexity bounds have not been proven for randomized algorithms. In particular, the seemingly obvious lower bounds of Ω(m) messages, where m is the number of edges in the network, and Ω(D) time, where D is the network diameter, are nontrivial to show for randomized (Monte Carlo) algorithms. (Recent results, showing that even Ω(n), where n is the number of nodes in the network, is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms, except for the restricted case of comparison algorithms, where it was also required that nodes may not wake up spontaneously and that D and n were not known. We establish these fundamental lower bounds in this article for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (namely, algorithms that work for all graphs), apply to every D, m, and n, and hold even if D, m, and n are known, all the nodes wake up simultaneously, and the algorithms can make any use of node's identities. To show that these bounds are tight, we present an O(m) messages algorithm. An O(D) time leader election algorithm is known. A slight adaptation of our lower bound technique gives rise to an Ω(m) message lower bound for randomized broadcast algorithms. 

An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. The answer is known to be negative in the deterministic setting. We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that tradeoff messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.

A Universal Flow Regime Map for Horizontal Two-Phase Flow in Pipes

A new universal flow map has been developed for two-phase co-current flow. The map has been successfully tested against wide variety of data. Flow regime transition predictors suggested by other authors have been shown to be useful. New transitional models are proposed for the stratified to annular regimes, blow through slug and intermittent regimes.

Graphs of relations and Hilbert series

We are discussing certain combinatorial and counting problems related to quadratic algebras. First we give examples which confirm the Anick conjecture on the minimal Hilbert series for algebras given by $n$ generators and $\frac {n(n-1)}{2}$ relations for $n \leq 7$. Then we investigate combinatorial structure of colored graph associated to relations of RIT algebra. Precise descriptions of graphs (maps) corresponding to algebras with maximal Hilbert series are given in certain cases. As a consequence it turns out, for example, that RIT algebra may have a maximal Hilbert series only if components of the graph associated to each color are pairwise 2-isomorphic.

Perceived and reported access to the general practitioner: an international comparison of universal access and mixed private/public systems.

Timely and convenient access to primary healthcare is essential for the health of the population as delays can incur additional health and financial costs. Access to health care is under increasing scrutiny as part of the drive to contain escalating costs, while attempting to maintain equity in service provision. The objective was to compare primary care services in Republic of Ireland and Northern Ireland, and to report on perceived and reported access to GP services in universal access and mixed private/public systems. A questionnaire study was performed in Northern Ireland (NI) and the Republic of Ireland (ROI). Patients of 20 practices in the ROI and NI were contacted (n = 22,796). Main outcome measures were overall satisfaction and the access to GP services. Individual responses and scale scores were derived using the General Practice Assessment Questionnaire (G-PAQ). The response rate was 52% (n = 11,870). Overall satisfaction with GP practices was higher in ROI than in NI (84.2% and 80.9% respectively). Access scores were higher in ROI than in NI (69.2% and 57.0% respectively) Less than 1 in 10 patients in ROI waited two or more working days to see a doctor of choice (8.1%) compared to almost half (45.0%) in NI. In NI overall satisfaction decreased as practice size increased; 82.8%, 80.4%, and 75.8%. In both systems, in large practices, accessibility is reduced when compared to smaller practices. The faster access to GP services in ROI may be due to the deterrent effect of the consultation charge freeing up services although, as it is the poorest and sickest who are deterred by the charge this improved accessibility may come at a significant cost in terms of equity. The underlying concern for policy makers centres around provision of equitable services.

Universal power quality manager with a new control scheme

A new universal power quality manager is proposed. The proposal treats a number of power quality problems simultaneously. The universal manager comprises a combined series and shunt three-phase PWM controlled converters sharing a common DC link. A control scheme based on fuzzy logic is introduced and the general features of the design and operation processes are outlined. The performance of two configurations of the proposed power quality manager are compared in terms of a recently formulated unified power quality index. The validity and integrity of the proposed system is proved through computer simulated experiments