Flow of a maxwell liquid fluid between two rotating coaxial cones having the same vertex

We consider the secondary flows arising in the motion of a Maxwell fluid between two rotating coaxial cones having the same vertex. We find that in any meridian plane passing through the common axis of the cones, the flow field is divided into two regions. Such a division of flow field was first reported by Bhatnagar and Rathna.

Voting Paths

We consider a variant of the popular matching problem here. The input instance is a bipartite graph $G=(\mathcal{A}\cup\mathcal{P},E)$, where vertices in $\mathcal{A}$ are called applicants and vertices in $\mathcal{P}$ are called posts. Each applicant ranks a subset of posts in an order of preference, possibly involving ties. A matching $M$ is popular if there is no other matching $M'$ such that the number of applicants who prefer their partners in $M'$ to $M$ exceeds the number of applicants who prefer their partners in $M$ to $M'$. However, the “more popular than” relation is not transitive; hence this relation is not a partial order, and thus there need not be a maximal element here. Indeed, there are simple instances that do not admit popular matchings. The questions of whether an input instance $G$ admits a popular matching and how to compute one if it exists were studied earlier by Abraham et al. Here we study reachability questions among matchings in $G$, assuming that $G=(\mathcal{A}\cup\mathcal{P},E)$ admits a popular matching. A matching $M_k$ is reachable from $M_0$ if there is a sequence of matchings $\langle M_0,M_1,\dots,M_k\rangle$ such that each matching is more popular than its predecessor. Such a sequence is called a length-$k$ voting path from $M_0$ to $M_k$. We show an interesting property of reachability among matchings in $G$: there is always a voting path of length at most 2 from any matching to some popular matching. Given a bipartite graph $G=(\mathcal{A}\cup\mathcal{P},E)$ with $n$ vertices and $m$ edges and any matching $M_0$ in $G$, we give an $O(m\sqrt{n})$ algorithm to compute a shortest-length voting path from $M_0$ to a popular matching; when preference lists are strictly ordered, we have an $O(m+n)$ algorithm. This problem has applications in dynamic matching markets, where applicants and posts can enter and leave the market, and applicants can also change their preferences arbitrarily. After any change, the current matching may no longer be popular, in which case we are required to update it. However, our model demands that we switch from one matching to another only if there is consensus among the applicants to agree to the switch. Hence we need to update via a voting path that ends in a popular matching. Thus our algorithm has applications here.

Max-Coloring Paths: Tight Bounds and Extensions

The max-coloring problem is to compute a legal coloring of the vertices of a graph G = (V, E) with a non-negative weight function w on V such that Sigma(k)(i=1) max(v epsilon Ci) w(v(i)) is minimized, where C-1, ... , C-k are the various color classes. Max-coloring general graphs is as hard as the classical vertex coloring problem, a special case where vertices have unit weight. In fact, in some cases it can even be harder: for example, no polynomial time algorithm is known for max-coloring trees. In this paper we consider the problem of max-coloring paths and its generalization, max-coloring abroad class of trees and show it can be solved in time O(vertical bar V vertical bar+time for sorting the vertex weights). When vertex weights belong to R, we show a matching lower bound of Omega(vertical bar V vertical bar log vertical bar V vertical bar) in the algebraic computation tree model.

Algorithms for Colouring Random k-colourable Graphs

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k greater than or equal to 3. The best known polynomial time approximation algorithms require n(delta) (for a positive constant delta depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be ii-coloured almost surely in polynomial time. In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into ii colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) greater than or equal to n(-1+is an element of) where is an element of is a constant greater than 1/4.

Exact bounds for distributed graph colouring

A distributed system is a collection of networked autonomous processing units which must work in a cooperative manner. Currently, large-scale distributed systems, such as various telecommunication and computer networks, are abundant and used in a multitude of tasks. The field of distributed computing studies what can be computed efficiently in such systems. Distributed systems are usually modelled as graphs where nodes represent the processors and edges denote communication links between processors. This thesis concentrates on the computational complexity of the distributed graph colouring problem. The objective of the graph colouring problem is to assign a colour to each node in such a way that no two nodes connected by an edge share the same colour. In particular, it is often desirable to use only a small number of colours. This task is a fundamental symmetry-breaking primitive in various distributed algorithms. A graph that has been coloured in this manner using at most k different colours is said to be k-coloured. This work examines the synchronous message-passing model of distributed computation: every node runs the same algorithm, and the system operates in discrete synchronous communication rounds. During each round, a node can communicate with its neighbours and perform local computation. In this model, the time complexity of a problem is the number of synchronous communication rounds required to solve the problem. It is known that 3-colouring any k-coloured directed cycle requires at least ½(log* k - 3) communication rounds and is possible in ½(log* k + 7) communication rounds for all k ≥ 3. This work shows that for any k ≥ 3, colouring a k-coloured directed cycle with at most three colours is possible in ½(log* k + 3) rounds. In contrast, it is also shown that for some values of k, colouring a directed cycle with at most three colours requires at least ½(log* k + 1) communication rounds. Furthermore, in the case of directed rooted trees, reducing a k-colouring into a 3-colouring requires at least log* k + 1 rounds for some k and possible in log* k + 3 rounds for all k ≥ 3. The new positive and negative results are derived using computational methods, as the existence of distributed colouring algorithms corresponds to the colourability of so-called neighbourhood graphs. The colourability of these graphs is analysed using Boolean satisfiability (SAT) solvers. Finally, this thesis shows that similar methods are applicable in capturing the existence of distributed algorithms for other graph problems, such as the maximal matching problem.

The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

A k-dimensional box is the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval oil the real line of the form a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-cubes. The threshold dimension of a graph G(V, E) is the smallest integer k such that E can be covered by k threshold spanning subgraphs of G. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n vertices with factor O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is NP-complete to determine whether a given split graph has boxicity at most 3. (C) 2010 Elsevier B.V. All rights reserved.

Simulation and graph mining tools for improving gene mapping efficiency

Gene mapping is a systematic search for genes that affect observable characteristics of an organism. In this thesis we offer computational tools to improve the efficiency of (disease) gene-mapping efforts. In the first part of the thesis we propose an efficient simulation procedure for generating realistic genetical data from isolated populations. Simulated data is useful for evaluating hypothesised gene-mapping study designs and computational analysis tools. As an example of such evaluation, we demonstrate how a population-based study design can be a powerful alternative to traditional family-based designs in association-based gene-mapping projects. In the second part of the thesis we consider a prioritisation of a (typically large) set of putative disease-associated genes acquired from an initial gene-mapping analysis. Prioritisation is necessary to be able to focus on the most promising candidates. We show how to harness the current biomedical knowledge for the prioritisation task by integrating various publicly available biological databases into a weighted biological graph. We then demonstrate how to find and evaluate connections between entities, such as genes and diseases, from this unified schema by graph mining techniques. Finally, in the last part of the thesis, we define the concept of reliable subgraph and the corresponding subgraph extraction problem. Reliable subgraphs concisely describe strong and independent connections between two given vertices in a random graph, and hence they are especially useful for visualising such connections. We propose novel algorithms for extracting reliable subgraphs from large random graphs. The efficiency and scalability of the proposed graph mining methods are backed by extensive experiments on real data. While our application focus is in genetics, the concepts and algorithms can be applied to other domains as well. We demonstrate this generality by considering coauthor graphs in addition to biological graphs in the experiments.

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.

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.

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.

Non-contractible non-edges in 2-connected graphs

Any pair of non-adjacent vertices forms a non-edge in a graph. Contraction of a non-edge merges two non-adjacent vertices into a single vertex such that the edges incident on the non-adjacent vertices are now incident on the merged vertex. In this paper, we consider simple connected graphs, hence parallel edges are removed after contraction. The minimum number of nodes whose removal disconnects the graph is the connectivity of the graph. We say a graph is k-connected, if its connectivity is k. A non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. Otherwise the non-edge is non-contractible. We focus our study on non-contractible non-edges in 2-connected graphs. We show that cycles are the only 2-connected graphs in which every non-edge is non-contractible. (C) 2010 Elsevier B.V. All rights reserved.

Macroscopic model of city traffic using bond graph modelling

Modelling of city traffic involves capturing of all the dynamics that exist in real-time traffic. Probabilistic models and queuing theory have been used for mathematical representation of the traffic system. This paper proposes the concept of modelling the traffic system using bond graphs wherein traffic flow is based on energy conservation. The proposed modelling approach uses switched junctions to model complex traffic networks. This paper presents the modelling, simulation and experimental validation aspects.

Characterizing and recognizing weak visibility polygons

A polygon is said to be a weak visibility polygon if every point of the polygon is visible from some point of an internal segment. In this paper we derive properties of shortest paths in weak visibility polygons and present a characterization of weak visibility polygons in terms of shortest paths between vertices. These properties lead to the following efficient algorithms: (i) an O(E) time algorithm for determining whether a simple polygon P is a weak visibility polygon and for computing a visibility chord if it exist, where E is the size of the visibility graph of P and (ii) an O(n2) time algorithm for computing the maximum hidden vertex set in an n-sided polygon weakly visible from a convex edge.

On kuhnels 9-vertex complex projective plane

We present an elementary combinatorial proof of the existence and uniqueness of the 9-vertex triangulation of C P2. The original proof of existence, due to Kuhnel, as well as the original proof of uniqueness, due to Kuhnel and Lassmann, were based on extensive computer search. Recently Arnoux and Marin have used cohomology theory to present a computer-free proof. Our proof has the advantage of displaying a canonical copy of the affine plane over the three-element field inside this complex in terms of which the entire complex has a very neat and short description. This explicates the full automorphism group of the Kuhnel complex as a subgroup of the automorphism group of this affine plane. Our method also brings out the rich combinatorial structure inside this complex.