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

JOURNAL OF GRAPH THEORY 2013年第1期72卷 72-89页

作者： Gaspers, Serge Mnich, Matthias Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria Tech Univ Eindhoven NL-5600 MB Eindhoven Netherlands

We study combinatorial and algorithmic questions around minimal feedback vertex sets (FVS) in tournament graphs. On the combinatorial side, we derive upper and lower bounds on the maximum number of minimal FVSs in an n-vertex tournament. We prove that every tournament on n vertices has at most 1.6740n minimal FVSs, and that there is an infinite family of tournaments, all having at least 1.5448n minimal FVSs. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal FVSs of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum-sized FVS in a tournament.

关键词： algorithms and data structures tournaments feedback vertex set polynomial delay combinatorial bounds

来源：评论

学校读者我要写书评

暂无评论

Construction Sequences and Certifying 3-connectivity

引用

ALGORITHMICA 2012年第1-2期62卷 192-208页

作者： Schmidt, Jens M. Free Univ Berlin Dept Comp Sci Berlin Germany

Tutte proved that every 3-vertex-connected graph G on more than 4 vertices has a contractible edge. Barnette and Grunbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from G to K (4) can be computed in O(|V|(2)) time by extending Barnette's and Grunbaum's theorem. As an application, we derive a certificate for the 3-vertex-connectivity of graphs that can be easily computed and verified.

关键词： algorithms and data structures Construction sequence 3-connected Certifying algorithm Tutte contraction Removable edges

来源：评论

学校读者我要写书评

暂无评论

Fast Elastic Peak Detection for Mass Spectrometry data Mining

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND data ENGINEERING 2012年第4期24卷 634-648页

作者： Zhang, Xin Shasha, Dennis Song, Yang Wang, Jason T. L. NYU Courant Inst Math Sci Dept Comp Sci New York NY 10012 USA New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA

We study a data mining problem concerning the elastic peak detection in 2D liquid chromatography-mass spectrometry (LC-MS) data. These data can be modeled as time series, in which the X-axis represents time points and the Y-axis represents intensity values. A peak occurs in a set of 2D LC-MS data when the sum of the intensity values in a sliding time window exceeds a user-determined threshold. The elastic peak detection problem is to locate all peaks across multiple window sizes of interest in the data set. We propose a new data structure, called a Shifted Aggregation Tree or AggTree for short, and use the data structure to find the different peaks. Our method, called PeakID, solves the elastic peak detection problem in 2D LC-MS data yielding neither false positives nor false negatives. The method works by first constructing an AggTree in a bottom-up manner from the given data set, and then searching the AggTree for the peaks in a top-down manner. We describe a state-space algorithm for finding the topology and structure of an efficient AggTree to be used by PeakID. Our experimental results demonstrate the superiority of the proposed method over other methods on both synthetic and real-world data.

关键词： Knowledge discovery from LC-MS data time series data mining bioinformatics computational proteomics algorithms and data structures

来源：评论

学校读者我要写书评

暂无评论

Algorithmic paradigms for stability-based cluster validity and model selection statistical methods, with applications to microarray data analysis

引用

THEORETICAL COMPUTER SCIENCE 2012年 428卷 58-79页

作者： Giancarlo, R. Utro, F. Univ Palermo Dipartimento Matemat & Informat I-90123 Palermo Italy IBM TJ Watson Res Ctr Yorktown Hts NY 10598 USA

The advent of high throughput technologies, in particular microarrays, for biological research has revived interest in clustering, resulting in a plethora of new clustering algorithms. However, model selection, i.e., the identification of the correct number of clusters in a dataset, has received relatively little attention. Indeed, although central for statistics, its difficulty is also well known. Fortunately, a few novel techniques for model selection, representing a sharp departure from previous ones in statistics, have been proposed and gained prominence for microarray data analysis. Among those, the stability-based methods are the most robust and best performing in terms of prediction, but the slowest in terms of time. It is very unfortunate that as fascinating and classic an area of statistics as model selection, with important practical applications, has received very little attention in terms of algorithmic design and engineering. In this paper, in order to partially fill this gap, we make the following contributions: (A) the first general algorithmic paradigm for stability-based methods for model selection;(B) reductions showing that all of the known methods in this class are an instance of the proposed paradigm;(C) a novel algorithmic paradigm for the class of stability-based methods for cluster validity, i.e., methods assessing how statistically significant is a given clustering solution;(D) a general algorithmic paradigm that describes heuristic and very effective speed-ups known in the literature for stability-based model selection methods. Since the performance evaluation of model selection algorithms is mainly experimental, we offer, for completeness and without even attempting to be exhaustive, a representative synopsis of known experimental benchmarking results that highlight the ability of stability-based methods for model selection and the computational resources that they require for the task. As a whole, the contributions of this paper generaliz

关键词： algorithms and data structures General statistics Analysis of massive datasets Machine learning Computational biology Bioinformatics

来源：评论

学校读者我要写书评

暂无评论

More efficient periodic traversal in anonymous undirected graphs

引用

THEORETICAL COMPUTER SCIENCE 2012年 444卷 60-76页

作者： Czyzowicz, Jurek Dobrev, Stefan Gasieniec, Leszek Ilcinkas, David Jansson, Jesper Klasing, Ralf Lignos, Ioannis Martin, Russell Sadakane, Kunihiko Sung, Wing-Kin CNRS LaBRI F-33405 Talence France Univ Bordeaux F-33405 Talence France Univ Quebec Outaouais Dept Informat Gatineau PQ J8X 3X7 Canada Slovak Acad Sci Inst Math Bratislava 84000 Slovakia Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England Ochanomizu Univ Bunkyo Ku Tokyo 1128610 Japan Univ Durham Dept Comp Sci Durham DH1 3LE England Natl Inst Informat Principles Informat Res Div Chiyoda Ku Tokyo 1018430 Japan Natl Univ Singapore Dept Comp Sci Singapore 117543 Singapore

We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it;for each node v, the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily;see Budach (1978) [1]. However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005)[4] described an algorithm for assigning port numbers and an oblivious agent (i.e., an agent with no memory) using it, such that the agent explores any graph with n nodes within the period 10n. When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gasieniec et al. (2008) [7] to be no more than 3.75n - 2 (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most (4 + 1/3)n - 4 for oblivious agents and a period length of at most 3.5n - 2 for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, 2.8n - 2, on the period length for the oblivious case. (c) 2012 Elsevier B.V. All rights reserved.

关键词： algorithms and data structures Graph exploration Periodic graph traversal Oblivious agent Constant-memory agent Three-layer partition

来源：评论

学校读者我要写书评

暂无评论

LP can be a cure for Parameterized Problems

LP can be a cure for Parameterized Problems

引用

29th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Narayanaswamy, N. S. Raman, Venkatesh Ramanujan, M. S. Saurabh, Saket IIT Madras Dept Comp Sci & Engn Chennai Tamil Nadu India Inst Math Sci Chennai 600113 Tamil Nadu India

ISBN: (纸本)9783939897354

We investigate the parameterized complexity of VERTEX COVER parameterized above the optimum value of the linear programming (LP) relaxation of the integer linear programming formulation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that even the most straightforward branching algorithm (after some preprocessing) results in an O*(2.6181(r)) algorithm for the problem where r is the excess of the vertex cover size over the LP optimum. We write O*(f(k)) for a time complexity of the form O(f(k)n(O(1))), where f(k) grows exponentially with k. Then, using known and new reductions, we give O*(2.6181(k)) algorithms for the parameterized versions of ABOVE GUARANTEE VERTEX COVER, ODD CYCLE TRANSVERSAL, SPLIT VERTEX DELETION AND ALMOST 2-SAT, and an O*(1.6181(k)) algorithm for KONIG VERTEX DELETION, VERTEX COVER PARAM BY OCT and VERTEX COVER PARAM BY KVD. These algorithms significantly improve the best known bounds for these problems. The notable improvement is the bound for ODD CYCLE TRANSVERSAL for which this is the first major improvement after the first algorithm that showed it fixed-parameter tractable in 2003. We also observe that using our algorithm, one can obtain a simple kernel for the classical vertex cover problem with at most 2k - O(log k) vertices.

关键词： algorithms and data structures Graph algorithms Parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Spectral Sparsification in the Semi-Streaming Setting

Spectral Sparsification in the Semi-Streaming Setting

引用

28th International Symposium on Theoretical Aspects of Computer Science (SATCS)

作者： Kelner, Jonathan A. Levin, Alex MIT Dept Math Cambridge MA 02139 USA

ISBN: (纸本)9783939897255

Let G be a graph with n vertices and m edges. A sparsifier of G is a sparse graph on the same vertex set approximating G in some natural way. It allows us to say useful things about G while considering much fewer than m edges. The strongest commonly-used notion of sparsification is spectral sparsification;H is a spectral sparsifier of G if the quadratic forms induced by the Laplacians of G and H approximate one another well. This notion is strictly stronger than the earlier concept of combinatorial sparsification. In this paper, we consider a semi-streaming setting, where we have only (O) over tilde (n) storage space, and we thus cannot keep all of G. In this case, maintaining a sparsifier instead gives us a useful approximation to G, allowing us to answer certain questions about the original graph without storing all of it. In this paper, we introduce an algorithm for constructing a spectral sparsifier of G with O(n log n/epsilon(2)) edges (where epsilon is a parameter measuring the quality of the sparsifier), taking (O) over tilde (m) time and requiring only one pass over G. In addition, our algorithm has the property that it maintains at all times a valid sparsifier for the subgraph of G that we have received. Our algorithm is natural and conceptually simple. As we read edges of G, we add them to the sparsifier H. Whenever H gets too big, we resparsify it in (O) over tilde (n) time. Adding edges to a graph changes the structure of its sparsifier's restriction to the already existing edges. It would thus seem that the above procedure would cause errors to compound each time that we resparsify, and that we should need to either retain significantly more information or reexamine previously discarded edges in order to construct the new sparsifier. However, we show how to use the information contained in H to perform this resparsification using only the edges retained by earlier steps in nearly linear time.

关键词： algorithms and data structures graph algorithms spectral graph theory sub-linear space algorithms spectral sparsification

来源：评论

学校读者我要写书评

暂无评论

algorithms for Internal Validation Clustering Measures in the Post Genomic Era

Algorithms for Internal Validation Clustering Measures in th...

引用

作者： Filippo Utro UNIVERSITA DEGLI STUDI DI PALERMO

学位级别：博士

Inferring cluster structure in microarray datasets is a fundamental task for the so-called -omic sciences. It is also a fundamental question in Statistics, data Analysis and Classification, in particular with regard to the prediction of the number of clusters in a dataset, usually established via internal validation measures. Despite the wealth of internal measures available in the literature, new ones have been recently proposed, some of them specifically for microarray data. In this dissertation, a study of internal validation measures is given, paying particular atten- tion to the stability based ones. Indeed, this class of measures is particularly prominent and promising in order to have a reliable estimate of the correct number of clusters in a dataset. For this kind of measures, a new general algorithmic paradigm is proposed here that highlights the richness of measures in this class and accounts for the ones already available in the literature. Moreover, some of the most representative data-driven validation measures are also considered. Extensive experiments on twelve benchmark microarray datasets are performed, using both Hierarchical and K-means clustering algorithms, in order to assess both the intrinsic ability of a measure to predict the correct number of clusters in a dataset and its merit relative to the other measures. Particular attention is given both to precision and speed. The main result is a hierarchy of internal validation measures in terms of precision and speed, highlighting some of their merits and limitations not reported before in the literature. This hierarchy shows that the faster the measure, the less accurate it is. In order to reduce the time performance gap between the fastest and the most precise measures, the technique of designing fast approxima- tion algorithms is systematically applied. The end result is a speed-up of many of the measures studied here that brings the gap between the fastest and the most precise within one order

关键词： algorithms and data structures Experimantal Analysis of algorithms General Statistics Analysis of Massive datasets Machine Learning Computational Biology Bioinformatics

来源：评论

学校读者我要写书评

暂无评论

Construction Sequences and Certifying 3-Connectedness

Construction Sequences and Certifying 3-Connectedness

引用

27th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Schmidt, Jens M. Freie Univ Dept Comp Sci Berlin Germany

ISBN: (纸本)9783939897163

Tutte proved that every 3-connected graph on more than 4 nodes has a contractible edge. Barnette and Grunbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from C to the K-4 can be computed in O(|V|(2)) time by extending Barnette and Grunbaum's theorem. As an application, we derive a certificate for the 3-connectedness of graphs that can be easily computed and verified.

关键词： algorithms and data structures construction sequence 3-connected certifying algorithm Tutte contraction removable edges

来源：评论

学校读者我要写书评

暂无评论

New method in information processing for maintaining an efficient dynamic ordered set

引用

Science in China(Series F) 2009年第8期52卷 1292-1301页

作者： XIN ShiQing WANG GuoJin Institute of Computer Graphics and Image Processing Zhejiang University Hangzhou 310027 China State Key Laboratory of CAD & CG Zhejiang University Hangzhou 310027 China

This paper investigates how to maintain an efficient dynamic ordered set of bit strings, which is an important problem in the field of information search and information processing. Generally, a dynamic ordered set is required to support 5 essential operations including search, insertion, deletion, max-value retrieval and next-larger-value retrieval. Based on previous research fruits, we present an advanced data structure named rich binary tree （RBT）, which follows both the binary-search-tree property and the digital-search-tree property. Also, every key K keeps the most significant difference bit （MSDB） between itself and the next larger value among K＇s ancestors, as well as that between itself and the next smaller one among its ancestors. With the new data structure, we can maintain a dynamic ordered set in O（L） time. Since computers represent objects in binary mode, our method has a big potential in application. In fact, RBT can be viewed as a general-purpose data structure for problems concerning order, such as search, sorting and maintaining a priority queue. For example, when RBT is applied in sorting, we get a linear-time algorithm with regard to the key number and its performance is far better than quick-sort. What is more powerful than quick-sort is that RBT supports constant-time dynamic insertion/deletion.

关键词： information processing dynamic ordered set algorithms and data structures rich binary tree

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：