Catálogo de publicaciones - libros

In this paper, we study a new problem of finding a convex drawing of graphs with a boundary. It is proved that every triconnected plane graph whose boundary is fixed with a star-shaped polygon admits a drawing in which every inner facial cycle is drawn as a convex polygon. Such a drawing, called an , can be obtained in linear time.

We consider a profit maximization problem where we are asked to price a set of items that are to be assigned to a set of customers. The items can be represented as the edges of an undirected (multi)graph , where an edge multiplicity larger than one corresponds to multiple copies of the same item. Each customer is interested in purchasing a bundle of edges of , and we assume that each bundle forms a simple path in . Each customer has a known budget for her respective bundle, and is interested only in that particular bundle. The goal is to determine item prices and a feasible assignment of items to customers in order to maximize the total profit. When the underlying graph is a path, we derive a fully polynomial time approximation scheme, complementing a recent NP-hardness result. If the underlying graph is a tree, and edge multiplicities are one, we show that the problem is polynomially solvable, contrasting its APX-hardness for the case of unlimited availability of items. However, if the underlying graph is a grid, and edge multiplicities are one, we show that it is even NP-complete to approximate the maximum profit to within a factor .

We consider the class of strip graphs, a generalization of interval graphs. Intervals are assigned to rows such that two vertices have an edge between them if either their intervals intersect or they belong to the same row. We show that recognition of the class of strip graphs is -complete even if all intervals are of length 2. Strip graphs are important to the study of job selection, where we need an equivalence relation to connect multiple intervals that belong to the same job.

The problem we consider is Job Interval Selection (JISP) on machines. In the single-machine case, this is equivalent to Maximum Independent Set on strip graphs. For machines, the problem is to choose a maximum number of intervals, one from each job, such that the resulting choices form an -colorable interval graph. We show the single-machine case to be fixed-parameter tractable in terms of the maximum number of overlapping rows. We also use a concatenation operation on strip graphs to reduce the -machine case to the 1-machine case. This shows that -machine JISP is fixed-parameter tractable in the total number of jobs.

We consider the problem of grooming paths in all-optical networks with tree topology so as to minimize the switching cost, measured by the total number of used ADMs. We first present efficient approximation algorithms with approximation factor of 2 ln () + (ln ()) for any fixed node degree bound and grooming factor , and 2ln + ( ln ) in unbounded degree directed trees, respectively. In the attempt of extending our results to general undirected trees we completely characterize the complexity of the problem in star networks by providing polynomial time optimal algorithms for ≤2 and proving the intractability of the problem for any fixed >2. While for general topologies the problem was known to be NP-hard not constant, the complexity for fixed values of was still an open question.

A known approach of detecting dense subgraphs () in large sparse graphs involves first computing the for on the graph, and then using these probability vectors to detect the communities, see Latapy and Pons [2005]. In this paper we focus on the first part of such an approach the computation of the probability vectors for the random walks, and propose a more efficient algorithm for computing these vectors in time complexity that is linear in the size of the output, in case the input graphs are restricted to a family of graphs of bounded arboricity. Such classes of graphs cover a large number of cases of interest, all minor closed graph classes (planar graphs, graphs of bounded treewidth etc) and random graphs within the preferential attachment model, see Barabási and Albert [1999]. Our approach is extensible to other models of computation (PRAM, BSP or out-of-core computation) and also w.h.p. stays within the same complexity bounds for Erdős Renyi graphs.

Ma and Spinrad have shown that every transitive orientation of a chordal comparability graph is the intersection of four linear orders. That is, chordal comparability graphs are comparability graphs of posets of dimension four. Among other uses, this gives an implicit representation of a chordal comparability graph using () integers so that, given two vertices, it can be determined in (1) time whether they are adjacent, no matter how dense the graph is. We give a linear-time algorithm for finding the four linear orders, improving on their bound of ().

Given a class of graphs , a graph is a probe graph of if its vertices can be partitioned into a set ℙ of probes and an independent set ℕ of nonprobes such that can be embedded into a graph of by adding edges between certain nonprobes. If the partition of the vertices is a part of the input we call a partitioned probe graph of . In this paper we show that there exists a polynomial-time algorithm for the recognition of partitioned probe graphs of comparability graphs. This immediately leads to a polynomial-time algorithm for the recognition of partitioned probe graphs of cocomparability graphs. We then show that a partitioned graph is a partitioned probe permutation graph if and only if is at the same time a partitioned probe graph of comparability and cocomparability graphs.

We discuss the complexity of computing various graph polynomials of graphs of fixed clique-width. We show that the chromatic polynomial, the matching polynomial and the two-variable interlace polynomial of a graph of clique-width at most with vertices can be computed in time (), where () ≤3 for the inerlace polynomial, () ≤2+1 for the matching polynomial and () ≤3 2 for the chromatic polynomial.

Branchwidth is a connectivity parameter of graphs closely related to treewidth. Graphs of treewidth at most can be generated algorithmically as the subgraphs of -trees. n this paper, we investigate the family of edge-maximal graphs of branchwidth , that we call -branches. The -branches are, just as the -trees, a subclass of the chordal graphs where all minimal separators have size . However, a striking difference arises when considering subgraph-minimal members of the family. Whereas is the only subgraph-minimal -tree, we show that for any ≥7 a minimal -branch having maximal cliques exists for any value of , except for =8,=2. We characterize subgraph-minimal -branches for all values of . Our investigation leads to a generation algorithm, that adds one or two new maximal cliques in each step, producing exactly the -branches.

Given an arbitrary graph =(,) and a proper interval graph =(,) with  ⊆  we say that is a of . The graph is called a of if, for any sandwich graph ′=(,′) with  ⊆ ′ ⊂ , ′ is not a proper interval graph. In this paper we give a time algorithm computing a minimal proper interval completion of an arbitrary graph. The output is a proper interval model of the completion.