Routes in a wireless network can be repaired reactively after node failures by broadcasting the message across the neighborhood of the failed node. This broadcast problem is easily solvable, if the neighborhood of every node in the network induces a connected subgraph of the communication graph. Graphs with this property are called locally connected. This paper considers the edge augmentation problem for undirected graphs G = (V, E) that asks for a minimum set E' of additional edges such that the neighborhoods defined by G induce connected subgraphs of the augmented graph G' = (V, E∪E'). We develop a practical approximation algorithm with an approximation factor of 1 + ln (|V|) for general graphs and a constant approximation factor for several special cases such as unit disk graphs (factor 3/2), d-quasi unit disk graphs having d ≥ √3-1 ≈ 0.732 (factor 11/6) or graphs with a constant maximum vertex degree. Additionally we prove the NP-completeness of the augmentation problem above and the related augmentation problem that asks for a locally connected graph.

During the analysis of packet log files from network experiments, the question arises which received packet belongs to which of the potentially many binary identical send events. We discuss this send-receive correlation problem for networks with local broadcast media. We can prove that assigning send and receive events is an NP-complete problem. However, there is a solution algorithm that is exponential only in the number of nodes; if the number of network nodes is fixed, its complexity is polynomial.

We consider graphs with d-dimensional integral vector weights and rational cost values associated with the edges. We analyze the problem of finding a minimum cost path between two given vertices such that the vector sum of all edges in the path equals a given target vector m. The present paper shows that there are polynomial time algorithms for finding such a minimum cost m-path if the dimension of the vector weights is bounded by a constant and the vector weights are represented unary, where the general version is NP-complete under various restrictions.

Efficient ways of analyzing families of graphs that are generated by a certain type of context-free graph grammars are considered. These graph grammars are called cellular graph grammars . They generate the same graph families as hyperedge replacement systems, but are defined in a way that supports complexity analysis. A characteristic called “finiteness” of graph properties are defined, and combinatorial algorithms are presented for deciding whether a graph language generated by a given cellular graph grammar contains a graph with a given finite graph property. Structural parameters are introduced that bound the complexity of the decision procedure and special cases for which the decision can be made in polynomial time are discussed. Extensions to graph grammars that are not context-free are also given. Our results provide explicit and efficient combinatorial algorithms where, so far, only the existence of algorithms has been shown, or the best known algorithms are highly inefficient.

Using hierarchical definitions we can describe very large graphs in small spaces. In this paper we discuss how such succinct graph descriptions can be used to speed up the solution of graph problems. We present the bottom-up method that solves graph problems without expanding the hierarchical description. This allows solutions that are efficient in terms of the hierarchical graph description instead of the size of the expanded graph. We exemplify the method by giving efficient solutions to connectivity problems on hierarchical graphs. Our results have applications in computer-aided design for integrated circuit design and other engineering problems.