Expected parallel time and sequential space complexity of graph and digraph problems

This paper determines upper bounds on the expected time complexity for a variety of parallel algorithms for undirected and directed random graph problems. For connectivity, biconnectivity, transitive closure, minimum spanning trees, and all pairs minimum cost paths, we prove the expected time to beO(log logn) for the CRCW PRAM (this parallel RAM machine allows resolution of write conflicts) andO(logn · log logn) for the CREW PRAM (which allows simultaneous reads but not simultaneous writes). We also show that the problem of graph isomorphism has expected parallel timeO(log logn) for the CRCW PRAM andO(logn) for the CREW PRAM. Most of these results follow because of upper bounds on the mean depth of a graph, derived in this paper, for more general graphs than was known before.For undirected connectivity especially, we present a new probabilistic algorithm which runs on a randomized input and has an expected running time ofO(log logn) on the CRCW PRAM, withO(n) expected number of processors only.Our results also improve known upper bounds on the expected space required for sequential graph algorithms. For example, we show that the problems of finding connected components, transitive closure, minimum spanning trees, and minimum cost paths have expected sequential spaceO(logn · log logn) on a deterministic Turing Machine. We use a simulation of the CRCW PRAM to get these expected sequential space bounds.This research was supported by National Science Foundation Grant DCR-85-03251 and Office of Naval Research Contract N00014-80-C-0647.This research was partially supported by the National Science Foundation Grants MCS-83-00630, DCR-8503497, by the Greek Ministry of Research and Technology, and by the ESPRIT Basic Research Actions Project ALCOM.     

An improved exact algorithm for the domatic number problem

The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time n^2.695 (up to polynomial factors) and in polynomial space. This result improves the previous bound of n^2.8805, which is due to Björklund and Husfeldt. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Δ(G) by a randomized polynomial-space algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Δ(G)?5. Our new randomized algorithm employs Schöning's approach to constraint satisfaction problems.     

Complexity analysis of a decentralised graph colouring algorithm

Colouring a graph with its chromatic number of colours is known to be NP-hard. Identifying an algorithm in which decisions are made locally with no information about the graph's global structure is particularly challenging. In this article we analyse the complexity of a decentralised colouring algorithm that has recently been proposed for channel selection in wireless computer networks.     

The game chromatic number and the game colouring number of classes of oriented cactuses

We prove that the game chromatic and the game colouring number of the class of orientations of cactuses with girth of 2 or 3 is 4. We improve this bound for the class of orientations of certain forest-like cactuses to the value of 3. These results generalise theorems on the game colouring number of undirected forests (Faigle et al., 1993 [3]) resp. orientations of forests (Andres, 2009 [1]). For certain undirected cactuses with girth 4 we also obtain the tight bound 4, thus improving a result of Sidorowicz (2007) [8].     

Self-stabilizing algorithms for efficient sets of graphs and trees

This paper presents distributed self-stabilizing algorithms to compute the efficiency of trees and optimally efficient sets of general graphs.     

Clean the graph before you draw it!

We prove a relationship between the Cleaning problem and the Balanced Vertex-Ordering problem, namely that the minimum total imbalance of a graph equals twice the brush number of a graph. This equality has consequences for both problems. On one hand, it allows us to prove the NP-completeness of the Cleaning problem, which was conjectured by Messinger et al. [M.-E. Messinger, R.J. Nowakowski, P. Pra?at, Cleaning a network with brushes, Theoret. Comput. Sci. 399 (2008) 191-205]. On the other hand, it also enables us to design a faster algorithm for the Balanced Vertex-Ordering problem [J. Kára, K. Kratochvíl, D. Wood, On the complexity of the balanced vertex ordering problem, Discrete Math. Theor. Comput. Sci. 9 (1) (2007) 193-202].     

Finding next-to-shortest paths in a graph

We study the problem of finding the next-to-shortest paths in a graph. A next-to-shortest (u,v)-path is a shortest (u,v)-path amongst (u,v)-paths with length strictly greater than the length of the shortest (u,v)-path. In contrast to the situation in directed graphs, where the problem has been shown to be NP-hard, providing edges of length zero are allowed, we prove the somewhat surprising result that there is a polynomial time algorithm for the undirected version of the problem.     

Worst case analysis of a greedy algorithm for graph thickness

In this paper, we consider a greedy algorithm for thickness of graphs. The greedy algorithm we consider here takes a maximum planar subgraph away from the current graph in each iteration and repeats this process until the current graph has no edge. The greedy algorithm outputs the number of iterations which is an upper bound of thickness for an input graph G=(V,E). We show that the performance ratio of the greedy algorithm is .     

The number of spanning trees of a graph with given matching number

The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. In this paper, we present sharp upper bounds for the number of spanning trees of a graph with given matching number.     

On simultaneous straight-line grid embedding of a planar graph and its dual

Simultaneous representations of planar graphs and their duals normally require that the dual vertices to be placed inside their corresponding primal faces, and the edges of the dual graph to cross only their corresponding primal edges. Erten and Kobourov [C. Erten, S.G. Kobourov, Simultaneous embedding of a planar graph and its dual on the grid, Theory Computer Systems 38 (2005) 313-327] provided a linear time algorithm on simultaneous straight-line grid embedding of a 3-connected planar graph and its dual such that all the vertices are placed on grid points and each edge is drawn as one straight-line segment except for one which is drawn using two segments. Their drawing size is (2n−2)×(2n−2), where n is the total number of vertices in the graph and its dual. They raised an open question on whether there is a large class of planar graphs that allows this simultaneous straight-line grid embedding on a smaller grid. We answer this open question by giving a linear time simultaneous straight-line grid embedding algorithm for a 3-connected planar graph and its dual on a grid of size (n−1)×n.     

A linear-time algorithm to compute a MAD tree of an interval graph

The average distance of a connected graph G is the average of the distances between all pairs of vertices of G. We present a linear time algorithm that determines, for a given interval graph G, a spanning tree of G with minimum average distance (MAD tree). Such a tree is sometimes referred to as a minimum routing cost spanning tree.     

A genetic algorithm for the uncapacitated single allocation planar hub location problem

Given a set of n interacting points in a network, the hub location problem determines location of the hubs (transfer points) and assigns spokes (origin and destination points) to hubs so as to minimize the total transportation cost. In this study, we deal with the uncapacitated single allocation planar hub location problem (PHLP). In this problem, all flow between pairs of spokes goes through hubs, capacities of hubs are infinite, they can be located anywhere on the plane and are fully connected, and each spoke must be assigned to only one hub. We propose a mathematical formulation and a genetic algorithm (PHLGA) to solve PHLP in reasonable time. We test PHLGA on simulated and real life data sets. We compare our results with optimal solution and analyze results for special cases of PHLP for which the solution behavior can be predicted. Moreover, PHLGA results for the AP and CAB data set are compared with other heuristics.     

Extremal values on the harmonic number of trees

Let G=(V(G), E(G)) be a simple connected graph. The harmonic number of G, denoted by H(G), is defined as the sum of the weights 2/(d(u)+d(v)) of all edges uv of G, where d(u) denotes the degree of a vertex u in G. In this paper, some extremal problems on the harmonic number of trees are studied. The extremal values on the harmonic number of trees with given graphic parameters, such as pendant number, matching number, domination number and diameter, are determined. The corresponding extremal graphs are characterized, respectively.