检索结果-内蒙古大学图书馆

IEEE International Conference on Acoustics, Speech, and Signal Processing

作者： Benjamin A. Miller Nadya T. Bliss Patrick J. Wolfe Lincoln Laboratory Massachusetts Institute of Technology Lexington Massachusetts 02420 Statistics and Information Sciences Laboratory Harvard University Cambridge Massachusetts 02138

ISBN: (纸本)9781424442959

graphs are canonical examples of high-dimensional non-Euclidean data sets, and are emerging as a common data structure in many fields. While there are many algorithms to analyze such data, a signal processing theory for evaluating these techniques akin to detection and estimation in the classical Euclidean setting remains to be developed. In this paper we show the conceptual advantages gained by formulating graph analysis problems in a signal processing framework by way of a practical example: detection of a subgraph embedded in a background graph. We describe an approach based on detection theory and provide empirical results indicating that the test statistic proposed has reasonable power to detect dense subgraphs in large random graphs.

关键词： Chi-squared test community detection graph algorithms high-dimensional data signal detection theory

来源：评论

学校读者我要写书评

暂无评论

Quantum approaches to graph colouring

引用

THEORETICAL COMPUTER SCIENCE 2009年第4-5期410卷 302-309页

作者： D'Hondt, Ellie Vrije Univ Brussel B-1050 Brussels Belgium

In this paper, we investigate quantum algorithms for graph colouring problems, in particular for 2- and 3-colouring of graphs. Our main goal is to establish a set of quantum representations and operations suitable for the problem at hand. We propose unitaryas well as measurement-based quantum computations, also taking inspiration from answer set programming, a form of declarative programming close to traditional logic programming. The approach used is one in which we first generate arbitrary solutions to the problem, then constraining these according to the problem's input. Though we do not achieve fundamental speed-ups, our algorithms show how quantum concepts can be used for programming and moreover exhibit structural differences. For example, we compute all possible colourings at the same time. We compare our algorithms with classical ones, highlighting how the same type of difficulties give rise to NP-complete behaviour, and propose possible improvements. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Quantum computing graph algorithms

来源：评论

学校读者我要写书评

暂无评论

graph Spanners in the Streaming Model: An Experimental Study

引用

ALGORITHMICA 2009年第2期55卷 346-374页

作者： Ausiello, Giorgio Demetrescu, Camil Franciosa, Paolo G. Italiano, Giuseppe F. Ribichini, Andrea Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00185 Rome Italy Univ Roma La Sapienza Dipartimento Stat Probabilita & Stat Applicate I-00185 Rome Italy

This article reports the results of an extensive experimental analysis of efficient algorithms for computing graph spanners in the data streaming model, where an (alpha, beta)-spanner of a graph G is a subgraph S subset of G such that for each pair of vertices the distance in S is at most a times the distance in G plus beta. To the best of our knowledge, this is the first computational study of graph spanner algorithms in a streaming setting. We compare experimentally the randomized algorithms proposed by Baswana (http://***/abstract?id=oai:***:cs/0611023) and by Elkin (In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw, Poland, pp. 716-727, 9-13 July 2007) for general stretch factors with the deterministic algorithm presented by Ausiello et al. (In: Proceedings of the 15th Annual European Symposium on algorithms (ESA 2007), Engineering and Applications Track, Eilat, Israel, 8-10 October 2007. LNCS, vol. 4698, pp. 605-617, 2007), designed for building small stretch spanners. All the algorithms we implemented work in a data streaming model where the input graph is given as a stream of edges in arbitrary order, and all of them need a single pass over the data. Differently from the algorithm in Ausiello et al., the algorithms in Baswana (http://***/abstract?id=oai:***:cs/0611023) and Elkin (In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw, Poland, pp. 716-727, 9-13 July 2007) need to know in advance the number of vertices in the graph. The results of our experimental investigation on several input families confirm that all these algorithms are very efficient in practice, finding spanners with stretch and size much smaller than the theoretical bounds and comparable to those obtainable by off-line algorithms. Moreover, our experimental findings confirm that small values of the stretch factor are the case of

关键词： graph algorithms graph spanners Data streams Experimental algorithmics Algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Clean the graph before you draw it!

引用

INFORMATION PROCESSING LETTERS 2009年第10期109卷 463-467页

作者： Gaspers, Serge Messinger, Margaret-Ellen Nowakowski, Richard J. Pralat, Pawel Dalhousie Univ Dept Math & Stat Halifax NS B3H 3J5 Canada Univ Montpellier 2 CNRS LIRMM F-34392 Montpellier France

We prove a relationship between the CLEANING problem and the BALANCED VERTEX-ORDERING problem, namely that the minimum total imbalance of a graph equals twice the brush number of a graph. This equality has consequences for both problems. On one hand, it allows us to prove the A(P-completeness of the CLEANING problem, which was conjectured by Messinger et al. [M.-E. Messinger, R.J. Nowakowski, P. Pralat, Cleaning a network with brushes, Theoret. Comput. Sci. 399 (2008) 191-205]. On the other hand, it also enables us to design a faster algorithm for the BALANCED VERTEX-ORDERING problem [J. Kara, K. Kratochvil, D. Wood, On the complexity of the balanced vertex ordering problem, Discrete Math. Theor. Comput. Sci. 9 (1) (2007) 193-202]. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Brush number Balanced vertex-ordering graph algorithms Computational complexity

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph

引用

INFORMATION PROCESSING LETTERS 2009年第23-24期109卷 1227-1231页

作者： Berczi, Kristof Fujishige, Satoru Kamiyama, Naoyuki Chuo Univ Dept Informat & Syst Engn Tokyo Japan Eotvos Lorand Univ Dept Operat Res H-1364 Budapest Hungary Kyoto Univ Math Sci Res Inst Kyoto 6068501 Japan

Suppose that we are given a directed graph D = (V, A) with specified vertices r(1), r(2) is an element of V. this paper, we consider the problem of discerning the existence of a pair of arc-disjoint spanning in-arborescence rooted at r(1) and out-arborescence rooted at r(2), and finding such arborescences if they exist. It is known (Bang-Jensen (1991) [1]) that this problem is NP-complete even if r(1) = r(2). As a special case, it is only known (Bang-Jensen (1991) [1]) that this problem in a tournament can be solved in polynomial time. In this paper, we give a linear-time algorithm for this problem in a directed acyclic graph. We also consider an extension of our problem to the case where we have multiple roots for in-arborescences and out-arborescences, respectively. (C) 2009 Elsevier B.V. All rights reserved.

关键词： graph algorithms Directed graph Arborescence Packing

来源：评论

学校读者我要写书评

暂无评论

On the graph turnpike problem

引用

INFORMATION PROCESSING LETTERS 2009年第14期109卷 774-776页

作者： Feder, Tomas Motwani, Rajeev Stanford Univ Dept Comp Sci Stanford CA 94305 USA

Results on graph turnpike problem without distinctness, including its NP-completeness, and an O(m+n log n) algorithm, is presented. The usual turnpike problem has all pairwise distances given, but does not specify which pair of vertices w_e corresponds to. There are two other problems that can be viewed as special cases of the graph turnpike problem, including the bandwidth problem and the low-distortion graph embedding problem. The aim for the turnpike problem in the NP-complete is to orient the edges with weights w_i in either direction so that when the whole cycle is transversed in the real line, it returns to a chosen starting point for the cycle. An instance of the turnpike problem with or without distinctness is uniquely mappable if there exists at most one solution up to translation and choice of orientation.

关键词： graph turnpike problem graph algorithms Computational geometry

来源：评论

学校读者我要写书评

暂无评论

A Path Following Algorithm for the graph Matching Problem

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2009年第12期31卷 2227-2242页

作者： Zaslavskiy, Mikhail Bach, Francis Vert, Jean-Philippe Mines ParisTech Ctr Computat Biol F-77305 Fontainebleau France Mines ParisTech Ctr Math Morphol F-77305 Fontainebleau France INSERM Inst Curie U900 F-75248 Paris 05 France INRIA Willow Project Team Lab Informat ENSCNRSUMR 8548 F-75214 Paris France

We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We, therefore, construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore, perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four data sets: simulated graphs, QAPLib, retina vessel images, and handwritten Chinese characters. In all cases, the results are competitive with the state of the art.

关键词： graph algorithms graph matching convex programming gradient methods machine learning classification image processing

来源：评论

学校读者我要写书评

暂无评论

Algorithmic graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction

引用

ALGORITHMICA 2009年第2期54卷 142-180页

作者： Demaine, Erik D. Hajiaghayi, MohammadTaghi Kawarabayashi, Ken-ichi MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan

We explore three important avenues of research in algorithmic graph-minor theory, which all stem from a key min-max relation between the treewidth of a graph and its largest grid minor. This min-max relation is a keystone of the graph Minor Theory of Robertson and Seymour, which ultimately proves Wagner's Conjecture about the structure of minor-closed graph properties. First, we obtain the only known polynomial min-max relation for graphs that do not exclude any fixed minor, namely, map graphs and power graphs. Second, we obtain explicit (and improved) bounds on the min-max relation for an important class of graphs excluding a minor, namely, K3, k-minor-free graphs, using new techniques that do not rely on graph Minor Theory. These two avenues lead to faster fixed-parameter algorithms for two families of graph problems, called minor-bidimensional and contraction-bidimensional parameters, which include feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex-removal parameters, dominating set, edge dominating set, R-dominating set, connected dominating set, connected edge dominating set, connected R-dominating set, and unweighted TSP tour. Third, we disprove a variation of Wagner's Conjecture for the case of graph contractions in general graphs, and in a sense characterize which graphs satisfy the variation. This result demonstrates the limitations of a general theory of algorithms for the family of contraction-closed problems (which includes, for example, the celebrated dominating-set problem). If this conjecture had been true, we would have had an extremely powerful tool for proving the existence of efficient algorithms for any contraction-closed problem, like we do for minor-closed problems via graph Minor Theory.

关键词： graph minors graph algorithms Grid graphs Treewidth Bidimensionality Wagner's conjecture

来源：评论

学校读者我要写书评

暂无评论

Algorithmic graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction

引用

17th International Symposium on algorithms and Computation (ISAAC 2006)

ISBN: (纸本)3540496947

关键词： graph minors graph algorithms Grid graphs Treewidth Bidimensionality Wagner's conjecture

来源：评论

学校读者我要写书评

暂无评论

Loss optimal monotone relabeling of noisy multi-criteria data sets

引用

INFORMATION SCIENCES 2009年第24期179卷 4089-4096页

作者： Rademaker, Michael De Baets, Bernard De Meyer, Hans Univ Ghent Dept Appl Math Biometr & Proc Control B-9000 Ghent Belgium Univ Ghent Dept Appl Math & Comp Sci B-9000 Ghent Belgium

A method to relabel noisy multi-criteria data sets is presented, taking advantage of the transitivity of the non-monotonicity relation to formulate the problem as an efficiently solvable maximum independent set problem. A framework and an algorithm for general loss functions are presented. and the flexibility of the approach is indicated by some examples, showcasing the ease with which the method can handle application-specific loss functions. Both didactical examples and real-life applications are provided, using the zero-one, the L1 and the squared loss functions, as well as combinations thereof. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Machine learning Monotonicity constraints graph algorithms Maximum independent set Monotone relabeling Data cleaning Multi-criteria decision making

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：