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

On the number of minimal separators in graphs

JOURNAL OF GRAPH THEORY 2018年第4期87卷 653-659页

作者： Gaspers, Serge Mackenzie, Simon UNSW Sydney Sydney NSW Australia CSIRO Data61 Canberra ACT Australia Carnegie Mellon Univ Pittsburgh PA 15213 USA

Weconsider the largest number of minimal separators a graph on n vertices can have. - We give a new proof that this number is in O((1+root 5/2)(n).n). We prove that this number is in omega(1.4457(n)), improving on the previous best lower bound of Omega(3(n/3)) subset of omega(1.4422(n)). This gives also an improved lower bound on the number of potential maximal cliques in a graph. We would like to emphasize that our proofs are short, simple, and elementary.

关键词： combinatorial bounds enumeration algorithms extremal combinatorics

来源：评论

学校读者我要写书评

暂无评论

Extended dualization: Application to maximal pattern mining

引用

THEORETICAL COMPUTER SCIENCE 2016年 618卷 107-121页

作者： Nourine, Lhouari Petit, Jean-Marc Univ Blaise Pascal CNRS LIMOS Clermont Ferrand France Univ Lyon CNRS INSA Lyon LIRIS Lyon France

The dualization in arbitrary posets is a well-studied problem in combinatorial enumeration and is a crucial step in many applications in logics, databases, artificial intelligence and pattern mining. The objective of this paper is to study reductions of the dualization problem on arbitrary posets to the dualization problem on boolean lattices, for which output quasi-polynomial time algorithms exist, Quasi-polynomial time algorithms are algorithms which run in no(logn) where n is the size of the input and output. We introduce convex embedding and poset reflection as key notions to characterize such reductions. As a consequence, we identify posets, which are not boolean lattices, for which the dualization problem remains in quasi-polynomial time and propose a classification of posets with respect to dualization. From these results, we study how they can be applied to maximal pattern mining problems. We deduce a new classification of pattern mining problems and we point out how known problems involving sequences and conjunctive queries patterns, fit into this classification. Finally, we explain how to adapt the seminal DUALIZE & ADVANCE algorithm to deal with such patterns. As far as we know, this is the first contribution to explicit non-trivial reductions for studying the hardness of maximal pattern mining problems and to extend the DUALIZE & ADVANCE algorithm for complex patterns. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Hypergraph dualization enumeration algorithms Patterns mining

来源：评论

学校读者我要写书评

暂无评论

Sublinear-space bounded-delay enumeration for massive network analytics: Maximal cliques 43

Sublinear-space bounded-delay enumeration for massive networ...

引用

43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016

作者： Conte, Alessio Grossi, Roberto Marino, Andrea Versari, Luca Dipartimento di Informatica Università di Pisa Pisa Italy Scuola Normale Superiore Pisa Italy

ISBN: (纸本)9783959770132

Due to the sheer size of real-world networks, delay and space become quite relevant measures for the cost of enumeration in network analytics. This paper presents efficient algorithms for listing maximum cliques in networks, providing the first sublinear-space bounds with guaranteed delay per enumerated clique, thus comparing favorably with the known literature. © Alessio Conte, Roberto Grossi, Andrea Marino, and Luca Versari.

关键词： enumeration algorithms Maximal cliques Network mining and analytics Reverse search Space efficiency

来源：评论

学校读者我要写书评

暂无评论

On Maximal Chain Subgraphs and Covers of Bipartite Graphs 27th

On Maximal Chain Subgraphs and Covers of Bipartite Graphs

引用

27th International Workshop on Combinatorial algorithms (IWOCA)

作者： Calamoneri, Tiziana Gastaldello, Mattia Mary, Arnaud Sagot, Marie-France Sinaimeri, Blerina Sapienza Univ Rome Via Salaria 113 I-00198 Rome Italy INRIA Villeurbanne France Univ Lyon 1 Univ Lyon LBBE CNRS UMR558 Villeurbanne France

ISBN: (纸本)9783319445434;9783319445427

In this paper, we address three related problems. One is the enumeration of all the maximal edge induced chain subgraphs of a bipartite graph, for which we provide a polynomial delay algorithm. We give bounds on the number of maximal chain subgraphs for a bipartite graph and use them to establish the input-sensitive complexity of the enumeration problem. The second problem we treat is the one of finding the minimum number of chain subgraphs needed to cover all the edges a bipartite graph. For this we provide an exact exponential algorithm with a non trivial complexity. Finally, we approach the problem of enumerating all minimal chain subgraph covers of a bipartite graph and show that it can be solved in quasi-polynomial time.

关键词： Chain subgraph cover problem enumeration algorithms Exact exponential algorithms

来源：评论

学校读者我要写书评

暂无评论

A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs

引用

algorithms FOR MOLECULAR BIOLOGY 2015年第1期10卷 20-20页

作者： Sacomoto, Gustavo Lacroix, Vincent Sagot, Marie-France INRIA Rhone Alpes F-38330 Montbonnot St Martin France Univ Lyon F-69000 Lyon France Univ Lyon 1 F-69365 Lyon France CNRS Lab Biometrie & Biol Evolut UMR5558 F-69622 Villeurbanne France

Background: The problem of enumerating bubbles with length constraints in directed graphs arises in transcriptomics where the question is to identify all alternative splicing events present in a sample of mRNAs sequenced by RNA-seq. Results: We present a new algorithm for enumerating bubbles with length constraints in weighted directed graphs. This is the first polynomial delay algorithm for this problem and we show that in practice, it is faster than previous approaches. Conclusion: This settles one of the main open questions from Sacomoto et al. (BMC Bioinform 13: 5, 2012). Moreover, the new algorithm allows us to deal with larger instances and possibly detect longer alternative splicing events.

关键词： Alternative splicing RNA-seq De Bruijn graphs Bubbles enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

Maximization of submodular functions: Theory and enumeration algorithms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2009年第1期198卷 102-112页

作者： Goldengorin, Boris Univ Groningen Dept Operat NL-9700 AV Groningen Netherlands

Submodular functions are powerful tools to model and solve either to optimality or approximately many operational research problems including problems defined on graphs. After reviewing some long-standing theoretical results about the structure of local and global maxima of submodular functions, Cherenin's selection rules and his Dichotomy Algorithm, we revise the above mentioned theory and show that our revision is useful for creating new non-binary branching algorithms and finding either approximation solutions with guaranteed accuracy or exact ones. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Maximization Submodular functions enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimal dominating sets in graph classes: Combinatorial bounds and enumeration

引用

THEORETICAL COMPUTER SCIENCE 2013年 487卷 82-94页

作者： Couturier, Jean-Francois Heggernes, Pinar van 't Hof, Pim Kratsch, Dieter Univ Lorraine LITA F-57045 Metz 01 France Univ Bergen Dept Informat N-5020 Bergen Norway

The number of minimal dominating sets that a graph on n vertices can have is known to be at most 1.7159(n). This upper bound might not be tight, since no examples of graphs with 1.5705(n) or more minimal dominating sets are known. For several classes of graphs, we substantially improve the upper bound on the number of minimal dominating sets. At the same time, we give algorithms for enumerating all minimal dominating sets, where the running time of each algorithm is within a polynomial factor of the proved upper bound for the graph class in question. In several cases, we provide examples of graphs containing the maximum possible number of minimal dominating sets for graphs in that class, thereby showing the corresponding upper bounds to be tight. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Minimal dominating sets enumeration algorithms Combinatorial bounds Graph classes

来源：评论

学校读者我要写书评

暂无评论

Optimization design of RFD set based on Genetic Algorithm

Optimization design of RFD set based on Genetic Algorithm

引用

2014 ISFMFE - 6th International Symposium on Fluid Machinery and Fluid Engineering

作者： Jiangyun Li Kai Guan Xiaofang Guo Wenwen Chen Zhichao Chen Department of Civil Engineering Wuhan University China China Nuclear Power Engineering Co. Ltd. Beijing China

ISBN: (纸本)9781510804159

RFD (Reverse flow divert) set is a kind of maintenance-free delivery system driving by compress-air. It intermittently discharges through its delivery pipe. Without moving part, the optimized design of RFD set is a critical technical for efficient and stable operation. The deficiencies of traditional enumeration algorithms and marginal utility method have been indicated. Then, as the main point of the paper, Genetic Algorithm is discussed to solve the multi-objective and multidimensional optimization problem. By comparing the results of the three optimization methods, we can have the superiority of GA. Based on the needs of flow and head in industry, serial design of RFD has been made by using GA, thus the relationships of the structural parameters and operational parameters have been analyzed. The conversion relationship between different density and viscosity in average flow has been provided, which will be beneficial for the RFD set design in industry.

关键词： enumeration algorithms Genetic Algorithm Marginal Utility Method RFD Radiation flux density Genetic Algorithm (GA) Optimal design Average flow

来源：评论

学校读者我要写书评

暂无评论

An enumerative algorithm for solving nonconvex dynamic DEA models

引用

OPTIMIZATION LETTERS 2013年第1期7卷 101-115页

作者： Soleimani-damaneh, M. Univ Tehran Coll Sci Sch Math Stat & Comp Sci Tehran Iran

This paper provides a recursive enumeration algorithm for solving the nonconvex dynamic DEA models, to obtain cost minimum under nonconvex technologies. The validity of the algorithm is proved through some theorems. An illustrative example as well as a computational discussion are given to demonstrate the advantages of the proposed algorithm.

关键词： Dynamic DEA FDH Nonconvex models enumeration algorithms Recursive algorithms

来源：评论

学校读者我要写书评

暂无评论

Parameterized top-K algorithms

引用

THEORETICAL COMPUTER SCIENCE 2013年 470卷 105-119页

作者： Chen, Jianer Kanj, Iyad A. Meng, Jie Xia, Ge Zhang, Fenghui Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA Depaul Univ Sch Comp Chicago IL 60604 USA Samsung R&D Ctr San Jose CA 95134 USA Lafayette Coll Dept Comp Sci Easton PA 18042 USA Google Kirkland Kirkland WA 98033 USA

We study algorithmic techniques that produce the best K solutions to an instance of a parameterized NP-hard problem whose solutions are associated with a scoring function. Our parameterized top-K algorithms proceed in two stages. The first stage is a structure algorithm that on a problem instance constructs a structure of feasible size, and the second stage is an enumerating algorithm that produces the K best solutions to the instance based on the structure. We show that many algorithm-design techniques for parameterized algorithms, such as branch-and-search, color coding, and bounded treewidth, can be adopted for designing efficient structure algorithms. We then develop new techniques that support efficient enumerating algorithms. In particular, we show that for a large class of well-known NP optimization problems, there are parameterized top-K algorithms that produce the best K solutions for the problems in feasible amount of average time per solution when the parameter value is small. Finally, we investigate the relation between fixed-parameter tractability and parameterized top-K algorithms. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Parameterized algorithms enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：