Catálogo de publicaciones - libros

For a graph G and a positive integer k , the k -power of G is the graph G ^ k with V ( G ) as its vertex set and {( u , v )| u , v  ∈  V ( G ),  d _ G ( u , v ) ≤  k } as its edge set where d _ G ( u , v ) is the distance between u and v in graph G . The k-Steiner root problem on a graph G asks for a tree T with V ( G ) ⊆  V ( T ) and G is the subgraph of T ^ k induced by V ( G ). If such a tree T exists, we call it a k-Steiner root of G . This paper gives a linear time algorithm for the 3-Steiner root problem. Consider an unrooted tree T with leaves one-to-one labeled by the elements of a set V . The k-leaf power of T is a graph, denoted $T_{L}^{k}$ , with $T_{L}^{k} = (V, E)$ , where E  = {( u , v ) | u , v  ∈  V   and   d _ T ( u , v ) ≤  k }. We call T a k -leaf root of $T_{L}^{k}$ . The k -leaf power recognition problem is to decide whether a graph has such a k -leaf root. The complexity of this problem is still open for k  ≥ 5 [6]. It can be solved in polynomial time if the ( k  − 2)-Steiner root problem can be solved in polynomial time [6]. Our result implies that the k -leaf power recognition problem can be solved in linear time for k  = 5.

Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts, and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomaration approach.

It has been shown in [9] that there exist planar digraphs that require exponential area in every upward straight-line planar drawing. On the other hand, upward poly-line planar drawings of planar graphs can be realized in Θ ( n ^2) area [9]. In this paper we consider families of DAGs that naturally arise in practice, like DAGs whose underlying graph is a tree ( directed trees ), is a bipartite graph ( directed bipartite graphs ), or is an outerplanar graph ( directed outerplanar graphs ). Concerning directed trees , we show that optimal Θ ( n log n ) area upward straight-line/poly-line planar drawings can be constructed. However, we prove that if the order of the neighbors of each node is assigned, then exponential area is required for straight-line upward drawings and quadratic area is required for poly-line upward drawings, results surprisingly and sharply contrasting with the area bounds for planar upward drawings of undirected trees. After having established tight bounds on the area requirements of planar upward drawings of several families of directed trees, we show how the results obtained for trees can be exploited to determine asymptotic optimal values for the area occupation of planar upward drawings of directed bipartite graphs and directed outerplanar graphs .

A linear-time algorithm that does not need a planar embedding is presented for the problem of computing two vertex-disjoint paths, each with prescribed endpoints, in an undirected 3-connected planar graph.

In this paper we describe together with an overview about other results the main ideas of our polynomial time approximation schemes for the maximum weight independent set problem (selecting a set of disjoint disks in the plane of maximum total weight) in disk graphs and for the maximum bisection problem (finding a partition of the vertex set into two subsets of equal cardinality with maximum number of edges between the subsets) in unit-disk graphs.

We study the competitive ratio of certain online algorithms for a well-studied class of load balancing problems. These algorithms are obtained and analyzed according to a method by Crescenzi et al (2004). We show that an exact analysis of their competitive ratio on certain “uniform” instances would resolve a fundamental conjecture by Caccetta and Häggkvist (1978). The conjecture is that any digraph on n nodes and minimum outdegree d must contain a directed cycle involving at most ⌈ n / d ⌉ nodes. Our results are the first relating this conjecture to the competitive analysis of certain algorithms, thus suggesting a new approach to the conjecture itself. We also prove that, on “uniform” instances, the analysis by Crescenzi et al (2004) gives only trivial upper bounds, unless we find a counterexample to the conjecture. This is in contrast with other (notable) examples where the same analysis yields optimal (non-trivial) bounds.

For a 3-colourable graph  G , the 3-colour graph of  G , denoted  $\mathcal{C}_3(G)$ , is the graph with node set the proper vertex 3-colourings of  G , and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of  G . We consider the following question : given  G , how easily can we decide whether or not  $\mathcal{C}_3(G)$ is connected? We show that the 3-colour graph of a 3-chromatic graph is never connected, and characterise the bipartite graphs for which  $\mathcal{C}_3(G)$ is connected. We also show that the problem of deciding the connectedness of the 3-colour graph of a bipartite graph is coNP-complete, but that restricted to planar bipartite graphs, the question is answerable in polynomial time.

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L -cycle cover is a cycle cover in which the length of every cycle is in the set L  ⊆ ℕ. We investigate how well L -cycle covers of minimum weight can be approximated. For undirected graphs, we devise a polynomial-time approximation algorithm that achieves a constant approximation ratio for all sets L . On the other hand, we prove that the problem cannot be approximated within a factor of 2 −  ε for certain sets  L . For directed graphs, we present a polynomial-time approximation algorithm that achieves an approximation ratio of O ( n ), where n is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated within a factor of o ( n ). To contrast the results for cycle covers of minimum weight, we show that the problem of computing L -cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well.

We deal with the asymptotic enumeration of combinatorial structures on planar maps. Prominent instances of such problems are the enumeration of spanning trees, bipartite perfect matchings, and ice models. The notion of an α -orientation unifies many different combinatorial structures, including the afore mentioned. We ask for the number of α -orientations and also for special instances thereof, such as Schnyder woods and bipolar orientations. The main focus of this paper are bounds for the maximum number of such structures that a planar map with n vertices can have. We give examples of triangulations with 2.37^ n Schnyder woods, 3-connected planar maps with 3.209^ n Schnyder woods and inner triangulations with 2.91^ n bipolar orientations. These lower bounds are accompanied by upper bounds of 3.56^ n , 8^ n , and 3.97^ n , respectively. We also show that for any planar map M and any α the number of α -orientations is bounded from above by 3.73^ n and we present a family of maps which have at least 2.598^ n α -orientations for n big enough.

We study a variation of the vertex cover problem where it is required that the graph induced by the vertex cover is connected. We prove that this problem is polynomial in chordal graphs, has a PTAS in planar graphs, is APX-hard in bipartite graphs and is 5/3-approximable in any class of graphs where the vertex cover problem is polynomial (in particular in bipartite graphs).