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

LISTING MAXIMAL SUBGRAPHS SATISFYING STRONGLY ACCESSIBLE PROPERTIES

SIAM JOURNAL ON DISCRETE MATHEMATICS 2019年第2期33卷 587-613页

作者： Conte, Alessio Grossi, Roberto Marino, Andrea Versari, Luca Natl Inst Informat Tokyo 1000003 Japan Univ Pisa I-56127 Pisa Italy

algorithms for listing the subgraphs satisfying a given property (e.g., being a clique, a cut, a cycle) fall within the general framework of set systems. A set system (U,F) consists of a ground set U (e.g., a network's nodes) and a family F subset of 2(U) of subsets of U that have the required property. For the problem of listing all sets in F maximal under inclusion, the ambitious goal is to cover a large class of set systems, preserving at the same time the efficiency of the enumeration. Among the existing algorithms, the best-known ones list the maximal subsets in time proportional to their number but may require exponential space. In this paper we improve the state of the art in two directions by introducing an algorithmic framework based on reverse search that, under standard suitable conditions, simultaneously (i) extends the class of problems that can be solved efficiently to strongly accessible set systems and (ii) reduces the additional space usage from exponential in vertical bar U vertical bar to stateless, i.e., with no additional memory usage other than that proportional to the solution size, thus accounting for just polynomial space.

关键词： enumeration algorithms graphs and set systems network mining and analytics MCCIS space efficiency polynomial delay

来源：评论

学校读者我要写书评

暂无评论

A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 767卷 26-33页

作者： Elbassioni, Khaled Rauf, Imran Ray, Saurabh Khalifa Univ Sci & Technol Masdar Inst POB 54224 Abu Dhabi U Arab Emirates Inst Business Adm Karachi Pakistan New York Univ Abu Dhabi Abu Dhabi U Arab Emirates

We consider the problem of enumerating all minimal hitting sets of a given hypergraph (V, R), where V is a finite set, called the vertex set and R. is a set of subsets of V called the hyperedges. We show that, when the hypergraph admits a balanced subdivision, then a recursive decomposition can be used to obtain efficiently all minimal hitting sets of the hypergraph. We apply this decomposition framework to get incremental polynomial-time algorithms for finding minimal hitting sets and minimal set covers for a number of hypergraphs induced by a set of points and a set of geometric objects. The set of geometric objects includes half-spaces, hyper-rectangles and balls, in fixed dimension. A distinguishing feature of the algorithms we obtain is that they admit an efficient global parallel implementation, in the sense that all minimal hitting sets can be generated in polylogarithmic time in vertical bar V vertical bar, vertical bar R vertical bar and the total number of minimal transversals M, using a polynomial number of processors. For half-spaces in R-2, we show that the above two enumeration problems can be solved, using a different technique, with amortized polynomial delay. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Geometric hypergraphs Minimal transversals enumeration algorithms Minimal set covers

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the maximal number of columns of a ?-modular integer matrix: bounds and computations

引用

MATHEMATICAL PROGRAMMING 2024年第1-2期206卷 61-89页

作者： Averkov, Gennadiy Schymura, Matthias BTU Cottbus Senftenberg Pl Deutsch Einheit 1 D-03046 Cottbus Germany

We study the maximal number of pairwise distinct columns in a ?-modular integer matrix with m rows. Recent results by Lee et al. provide an asymptotically tight upper bound of O (m(2)) for fixed ?. We complement this ... 详细信息

关键词： ?-modular matrices Subdeterminants enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

algorithms for generating convex sets in acyclic digraphs

引用

JOURNAL OF DISCRETE algorithms 2009年第4期7卷 509-518页

作者： Balister, P. Gerke, S. Gutin, G. Johnstone, A. Reddington, J. Scott, E. Soleimanfallah, A. Yeo, A. Univ Memphis Dept Math Sci Memphis TN 38152 USA Royal Holloway Univ London Dept Math Egham TW20 0EX Surrey England Royal Holloway Univ London Dept Comp Sci Egham TW20 0EX Surrey England

A set X of vertices of an acyclic digraph D is convex if X not equal empty set and there is no directed path between vertices of X which contains a vertex not in X. A set X is connected if X not equal empty set and the underlying undirected graph of the subgraph of D induced by X is connected. Connected convex sets and convex sets of acyclic digraphs are of interest in the area of modern embedded processor technology. We construct an algorithm A for enumeration of all connected convex sets of an acyclic digraph D of order n. The time complexity of A is O(n . cc(D)), where cc(D) is the number of connected convex sets in D. We also give an optimal algorithm for enumeration of all (not just connected) convex sets of an acyclic digraph D of order n. In computational experiments we demonstrate that our algorithms outperform the best algorithms in the literature. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Convex sets Acyclic digraphs enumeration algorithms Embedded processors

来源：评论

学校读者我要写书评

暂无评论

On the Number of Simple Arrangements of Five Double Pseudolines

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2011年第2期45卷 279-302页

作者： Ferte, Julien Pilaud, Vincent Pocchiola, Michel Univ Paris 06 Equipe Combinatoire & Optimisat Paris France Univ Aix Marseille 1 Lab Informat Fondamentale Marseille France

We describe an incremental algorithm to enumerate the isomorphism classes of double pseudoline arrangements. The correction of our algorithm is based on the connectedness under mutations of the spaces of one-extensions of double pseudoline arrangements, proved in this paper. Counting results derived from an implementation of our algorithm are also reported.

关键词： Combinatorial geometry Convexity Two-dimensional projective geometries Arrangements of pseudolines Arrangements of double pseudolines Chirotopes Mutations One-extension spaces enumeration 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

来源：评论

学校读者我要写书评

暂无评论

Generalized Algorithm for Restricted Weak Composition Generation: Generation Algorithm for Second-Order Restricted Weak Compositions

引用

Journal of Mathematical Modelling and algorithms 2013年第4期12卷 345-372页

作者： Page, Daniel R. not available Winnipeg MB R2C 2Z2 Box 4 GRP555 RR5 Canada

This paper presents a new algorithm that arrives at a generalized solution for the generation of restricted weak compositions of n-parts. In particular, this generalized algorithm covers many commonly sought compositions such as bounded compositions, restricted compositions, weak compositions, and restricted part compositions. Introduced is an algorithm for generating generalized types of restricted weak compositions called first-order, and second-order restricted weak compositions. © 2012 Springer Science+Business Media B.V.

关键词： Combinatorics Computational number theory enumeration enumeration algorithms Generalized algorithms Generalized compositions Generation algorithms Integer compositions Restricted compositions Restricted weak compositions Weak integer compositions

来源：评论

学校读者我要写书评

暂无评论

An Efficient Algorithm for Enumerating Induced Subgraphs with Bounded Degeneracy 12th

An Efficient Algorithm for Enumerating Induced Subgraphs wit...

引用

12th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Wasa, Kunihiro Uno, Takeaki Natl Inst Informat Tokyo Japan

ISBN: (纸本)9783030046514;9783030046507

We propose a polynomial delay and polynomial space algorithm for the enumeration of k-degenerate induced subgraphs in a given graph. A graph G is k-degenerate if each of its induced subgraphs has a vertex of degree at most k. The degeneracy is considered as an indicator of the sparseness of the graph. Real-world graphs such as road networks, social networks and internet networks often have small degeneracy. Compared to other kinds of graph classes, bounded degeneracy does not give many structural properties such as induced subgraph free, or minor free. From this, using bounded degeneracy to reduce the time complexity is often not trivial. In this paper, we investigate ways of handling the degeneracy and propose an efficient algorithm for the k-degenerate induced subgraph enumeration. The time complexity is O (min {Delta + kk', (k')(2)}) time per solution with polynomial preprocessing time and the space complexity is linear in the input graph size, where Delta and k' are the maximum degree and the degeneracy of the input graph.

关键词： Graph algorithms enumeration algorithms Polynomial delay k-degenerate graphs

来源：评论

学校读者我要写书评

暂无评论

Enumerating Minimal Dominating Sets in Triangle-Free Graphs 36

Enumerating Minimal Dominating Sets in Triangle-Free Graphs

引用

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

作者： Bonamy, Marthe Defrain, Oscar Heinrich, Marc Raymond, Jean-Florent Univ Bordeaux CNRS Bordeaux France Univ Clermont Auvergne LIMOS Clermont Ferrand France Univ Claude Bernard LIRIS Lyon France Tech Univ Berlin LaS Team Berlin Germany

ISBN: (纸本)9783959771009

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we prove that this is the case in triangle-free graphs. This answers a question of Kante et al. Additionally, we show that deciding if a set of vertices of a bipartite graph can be completed into a minimal dominating set is a NP-complete problem.

关键词： enumeration algorithms output-polynomial algorithms minimal dominating set triangle-free graphs split graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：