On the tractability of coloring semirandom graphs

As part of the efforts to understand the intricacies of the k-colorability problem, different distributions over k-colorable graphs have been analyzed. While the problem is notoriously hard (not even reasonably approximable) in the worst case, the average case (with respect to such distributions) often turns out to be “easy”. Semi-random models mediate between these two extremes and are more suitable to imitate “real-life” instances than purely random models. In this work we consider semi-random variants of the planted k-colorability distribution. This continues a line of research pursued by Coja-Oghlan, and by Krivelevich and Vilenchik. Our aim is to study a more general semi-random framework than those suggested so far. On the one hand we show that previous algorithmic techniques extend to our more general semi-random setting; on the other hand we give a hardness result, proving that a closely related semi-random model is intractable. Thus we provide some indication about which properties of the input distribution make the k-colorability problem hard.     

Fast online graph clustering via Erd?s-Rényi mixture

In the context of graph clustering, we consider the problem of simultaneously estimating both the partition of the graph nodes and the parameters of an underlying mixture of affiliation networks. In numerous applications the rapid increase of data size over time makes classical clustering algorithms too slow because of the high computational cost. In such situations online clustering algorithms are an efficient alternative to classical batch algorithms. We present an original online algorithm for graph clustering based on a Erd?s-Rényi graph mixture. The relevance of the algorithm is illustrated, using both simulated and real data sets. The real data set is a network extracted from the French political blogosphere and presents an interesting community organization.     

Shape from shading using graph cuts

In this paper, we investigate the applicability of graph cuts to the SFS (shape-from-shading) problem. We propose a new semi-global method for SFS using graph cuts. The new algorithm combines the local method proposed by Lee and Rosenfeld [C.H. Lee, A. Rosenfeld, Improved methods of estimating shape from shading using the light source coordinate system, Artif. Intell. 26 (1985) 125-143] and a global method using an energy minimization technique. By employing a new global energy minimization formulation, the convex/concave ambiguity problem of Lee and Rosenfeld's method can be resolved efficiently. A new combinatorial optimization technique, the graph cuts method, is used for the minimization of the proposed energy functional. Experimental results on a variety of synthetic and real-world images show that the proposed algorithm reconstructs the 3-D shape of objects very efficiently.     

Fixed-Parameter Complexity of Minimum Profile Problems

The profile of a graph is an integer-valued parameter defined via vertex orderings; it is known that the profile of a graph equals the smallest number of edges of an interval supergraph. Since computing the profile of a graph is an NP-hard problem, we consider parameterized versions of the problem. Namely, we study the problem of deciding whether the profile of a connected graph of order n is at most n−1+k, considering k as the parameter; this is a parameterization above guaranteed value, since n−1 is a tight lower bound for the profile. We present two fixed-parameter algorithms for this problem. The first algorithm is based on a forbidden subgraph characterization of interval graphs. The second algorithm is based on two simple kernelization rules which allow us to produce a kernel with linear number of vertices and edges. For showing the correctness of the second algorithm we need to establish structural properties of graphs with small profile which are of independent interest. A preliminary version of the paper is published in Proc. IWPEC 2006, LNCS vol. 4169, 60–71.     

Compact separator decompositions in dynamic trees and applications to labeling schemes

This paper presents an efficient scheme maintaining a separator decomposition representation in dynamic trees using asymptotically optimal labels. In order to maintain the short labels, the scheme uses relatively low message complexity. In particular, if the initial dynamic tree contains only the root, then the scheme incurs an O(log⁴ n) amortized message complexity per topology change, where n is the current number of vertices in the tree. As a separator decomposition is a fundamental decomposition of trees used extensively as a component in many static graph algorithms, our dynamic scheme for separator decomposition may be used for constructing dynamic versions to these algorithms. The paper then shows how to use our dynamic separator decomposition to construct efficient labeling schemes on dynamic trees, using the same message complexity as our dynamic separator scheme. Specifically, we construct efficient routing schemes on dynamic trees, for both the designer and the adversary port models, which maintain optimal labels, up to a multiplicative factor of O(log log n). In addition, it is shown how to use our dynamic separator decomposition scheme to construct dynamic labeling schemes supporting the ancestry and NCA relations using asymptotically optimal labels, as well as to extend a known result on dynamic distance labeling schemes. Supported in part at the Technion by an Aly Kaufman fellowship. Supported in part by a grant from the Israel Science Foundation.     

Monotony properties of connected visible graph searching

Search games are attractive for their correspondence with classical width parameters. For instance, the invisible search number (a.k.a. node search number) of a graph is equal to its pathwidth plus 1, and the visible search number of a graph is equal to its treewidth plus 1. The connected variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on monotone search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an n-node graph is at most O(logn) times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is Ω(logn). Second, we prove that, as opposed to the non-connected variant of visible graph searching, “recontamination helps” for connected visible search. Precisely, we prove that, for any k4, there exists a graph with connected visible search number at most k, and monotone connected visible search number >k     

Differencing and merging of architectural views

Differencing and merging architectural views is an important activity in software engineering. However, existing approaches are still based on restrictive assumptions, such as requiring view elements to have unique identifiers or exactly matching types, which is often not the case in many application domains. We propose an approach based on structural information. We generalize a published polynomial-time tree-to-tree correction algorithm that detects inserts, renames and deletes, into a novel algorithm that additionally detects restricted moves. Our algorithm also supports forcing and preventing matches between view elements. We incorporate the algorithm into tools to compare and merge Component-and-Connector (C&C) architectural views. We provide an empirical evaluation of the algorithm. We illustrate the tools using extended examples, and use them to detect and reconcile interesting differences between real architectural views. This article is an expanded version of the following paper: Abi-Antoun, M., Aldrich, J., Nahas, N., Schmerl, B., and Garlan, D: 2006, ‘Differencing and Merging of Architectural Views’. In: Proceedings of the 21st IEEE International Conference on Automated Software Engineering, pp. 47–58.     

A new graph cut-based multiple active contour algorithm without initial contours and seed points

This paper presents a new graph cut-based multiple active contour algorithm to detect optimal boundaries and regions in images without initial contours and seed points. The task of multiple active contours is framed as a partitioning problem by assuming that image data are generated from a finite mixture model with unknown number of components. Then, the partitioning problem is solved within a divisive graph cut framework where multi-way minimum cuts for multiple contours are efficiently computed in a top-down way through a swap move of binary labels. A split move is integrated into the swap move within that framework to estimate the model parameters associated with regions without the use of initial contours and seed points. The number of regions is also estimated as a part of the algorithm. Experimental results of boundary and region detection of natural images are presented and analyzed with precision and recall measures to demonstrate the effectiveness of the proposed algorithm.     

基于文档标引图模型的文本相似度策略

文档标引图是一种基于短语的图结构文本特征表示模型,能更加全面、准确地表达文本特征信息,实现渐增的文本聚类和信息处理。该文基于文档标引图特征模型,提出文档相似度计算加法策略和乘法策略,采用变换函数对文档相似度值进行调整,增强文档之间的可区分性,改进文本聚类和分类等处理的性能,实例证明了策略的有效性。