Catálogo de publicaciones - libros

Motivated by the , we propose a simple and deterministic message passing algorithm for the Graph Bisection problem and related problems. The running time of the main algorithm is linear w.r.t. the number of vertices and edges. For evaluating its average-case correctness, planted solution models are used. For the Graph Bisection problem under the standard planted solution model with probability parameters and , we prove that our algorithm yields a planted solution with probability >1– if –=Ω(log(/)).

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

A random geometric graph is obtained by spreading points uniformly at random in a unit square, and by associating a vertex to each point and an edge to each pair of points at Euclidian distance at most . Such graphs are extensively used to model wireless ad-hoc networks, and in particular sensor networks. It is well known that, over a critical value of , the graph is connected with high probability.

In this paper we study the robustness of the connectivity of random geometric graphs in the supercritical phase, under deletion of edges. In particular, we show that, for a sufficiently large , any cut which separates two components of Θ() vertices each contains Ω() edges with high probability. We also present a simple algorithm that, again with high probability, computes one such cut of size (). From these two results we derive a constant expected approximation algorithm for the -balanced cut problem on random geometric graphs: find an edge cut of minimum size whose two sides contain at least vertices each.

This paper studies the problem of finding the 1-center on a graph where vertex weights are uncertain and the uncertainty is characterized by given intervals. It is required to find a minmax-regret solution, which minimizes the worst-case loss in the objective function. Averbakh and Berman had an (log )-time algorithm for the problem on a general graph. On a tree, the time complexity of their algorithm becomes (). In this paper, we improve these two bounds to (log ) and (log), respectively.

In the , we want to compute a set of node-disjoint simple paths in an undirected bipartite graph covering as many nodes as possible of one layer of the graph, with the constraint that all paths have both endpoints in the other layer. This is a variation of the that finds important applications in the design of molecular quantum-dot cellular automata (QCA) circuits and physical synthesis in VLSI. It also generalizes the maximum weight node-disjoint path cover problem. We show that MSS is NP-complete, present a polynomial-time -approximation algorithm, and show that it cannot be approximated with a factor better than unless = .

We deal with the problem of finding such an orientation of a given graph that the largest number of edges leaving a vertex (called the outdegree of the orientation) is small.

For any ∈(0,1) we show an time algorithm which finds an orientation of an input graph with outdegree at most ⌈(1+)⌉, where is the maximum density of a subgraph of . It is known that the optimal value of orientation outdegree is ⌈ ⌉.

Our algorithm has applications in constructing labeling schemes, introduced by Kannan in [18] and in approximating such graph density measures as arboricity, pseudoarboricity and maximum density. Our results improve over the previous, 2-approximation algorithms by Aichholzer [1] (for orientation / pseudoarboricity), by Arikati [3] (for arboricity) and by Charikar [5] (for maximum density).

In this paper, we study two variants of the bin packing /covering problems called and problems, and present new approximation algorithms for each of them. For the offline MRBP problem, the previous best known approximation ratio is , achieved by the classical First-Fit-Increasing () algorithm [1]. In this paper, we give a new -type algorithm with an approximation ratio of . For the offline LBC problem, it has been shown in [2] that the classical First-Fit-Decreasing () algorithm achieves an approximation ratio of . In this paper, we present a new -type algorithm with an approximation ratio of . Both algorithms are simple, run in near linear time (i.e., ( log)), and therefore are practical.

Let =(,) denote a weighted graph of nodes and edges, and let [ ′ ] denote the subgraph of induced by a subset of nodes ′ ⊆ . The of [ ′ ] is the maximum length of a shortest path in [ ′ ] emanating from its (i.e., a node of [ ′ ] of minimum eccentricity). In this paper, we focus on the problem of partitioning the nodes of into exactly non-empty subsets, so as to minimize the of the induced subgraph radii. We show that this problem – which is of significance in facility location applications – is NP-hard when is part of the input, but for a fixed constant > 2 it can be solved in (/!) time. Moreover, for the notable case =2, we present an efficient (+ log) time algorithm.

We show that -uniform hypertrees can be encoded in linear time using as little as –2 integers in the range [1,]. The decoding algorithm also runs in linear time. For general hypertrees, we require codes of length +–2, where is the number of hyperedges. We show that there are at most distinct labeled -uniform hypertrees, where (,) is a lower bound on the number of trees with vertex degrees exceeding . We suggest a counting scheme for determining (,).

Many interesting results that improve on the exponential running times of exact algorithms for NP-hard problems have been obtained in recent years. One example that has attracted quite some attention of late is , the problem of finding nodes that cover at least edges in a graph. Following the first proof of fixed-parameter tractability, several algorithms for this problem have been presented in rapid succession. We improve on the best known runtime bound, designing and analyzing an intuitive randomized algorithm that takes no more than (2.0911) steps. In fact, we observe and encourage a renewed vigor towards the design of intuitive algorithms within the community. That is, we make a plea to prefer simple, comprehendable, easy-to-implement and easy-to-verify algorithms at the expense of a more involved analysis over more complicated algorithms that are specifically tailored to ease the analysis.