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

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

JOURNAL OF GRAPH THEORY 2006年第3期53卷 209-232页

作者： Boros, Endre Elbassioni, Khaled Gurvich, Vladimir Rutgers State Univ RUTCOR Piscataway NJ 08854 USA Max Planck Inst Informat Saarbrucken Germany

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti-vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d-factors in bipartite graphs, and perfect 2-matchings in general graphs. (C) 2006 Wiley Periodicals, Inc.

关键词： bipartite graphs perfect matchings blockers generation algorithms matchable graphs

来源：评论

学校读者我要写书评

暂无评论

An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation

引用

DISCRETE APPLIED MATHEMATICS 2006年第16期154卷 2350-2372页

作者： Khachiyan, Leonid Boros, Endre Elbassioni, Khaled Gurvich, Vladimir Rutgers State Univ Dept Comp Sci Piscataway NJ 08854 USA Rutgers State Univ RUTCOR Piscataway NJ 08854 USA Max Planck Inst Informat D-66123 Saarbrucken Germany

Given a finite set V, and a hypergraph H subset of 2(V), the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. algorithms 21 (1996) 618-628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time. More generally, we consider a monotone property pi over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50-63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying pi and all maximal subsets not satisfying, for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties pi. (c) 2006 Elsevier B.V. All rights reserved.

关键词： dualization hypergraph transversals generation algorithms monotone properties frequent sets empty boxes

来源：评论

学校读者我要写书评

暂无评论

Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order

引用

DISCRETE APPLIED MATHEMATICS 2019年 268卷 223-236页

作者： Pai, Kung-Jui Chang, Jou-Ming Wu, Ro-Yu Chang, Shun-Chieh Ming Chi Univ Technol Dept Ind Engn & Management New Taipei Taiwan Natl Taipei Univ Business Inst Informat & Decis Sci Taipei Taiwan Lunghwa Univ Sci & Technol Dept Ind Management Taoyuan Taiwan Cybersecur Technol Inst Inst Informat Ind Taipei Taiwan Saim Univ Int Sino Coll Bangkok Thailand

A new type of sequences called left-child sequences (LC-sequences for short) was recently introduced by Wu et al. (2014) for representing binary trees. They pointed out that such sequences have a natural interpretation from the view point of data structure and gave a characterization of them. Based on this characterization, there is an easily implementing algorithm that uses generate-and-test approach to filter all LC-sequences of binary trees with n internal nodes in lexicographic order, while in general it is not efficient at all. In this paper, we first design two novel rotations that allow us to drastically alter the shape of binary trees (and thus their corresponding LC-sequences). As an application, these operations can be employed to generate all LC-sequences in lexicographic order. Accordingly, we present a more efficient algorithm associated with the new types of rotations for generating all LC-sequences and show that it takes only constant amortized running cost. Moreover, we extend our study to the ranking and unranking problems. By integrating a measure called "left distances" introduced by Makinen (1987) to represent binary trees, we develop efficient ranking and unranking algorithms for LC-sequences in lexicographic order. With the help of aggregate analysis, we show that both ranking and unranking algorithms can be run in amortized cost of O(n) time and space. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Binary trees Left-child sequences generation algorithms Ranking/unranking algorithms Lexicographic order Amortized cost

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

generation of Records Obtained from Sequences of Independent and Non-Identically Distributed Variables

引用

VESTNIK ST PETERSBURG UNIVERSITY-MATHEMATICS 2023年第4期56卷 540-548页

作者： Petukhov, S. A. Stepanov, A. V. Immanuel Kant Balt Fed Univ Educ & Res Cluster Inst High Technol Higher Sch Comp Sci & Appl Math Kaliningrad 236041 Russia

generation algorithms of record times and values obtained from sequences of independent and non-identically distributed random variables, the distribution functions of which are defined on a common support, are proposed in the present paper. Known algorithms of generation of record times and values are given in Introduction for the case when the initial random variables are independent and identically distributed. A brief review of the scientific literature associated with this topic is also given in Introduction. It is also pointed out there that all efficient algorithms of record generation are based on the Markov property of records. In Section 2, the distribution functions of record times and values are derived for the case when the initial random variables are independent and non-identically distributed. The corresponding record-generation algorithms are proposed for the first time. These algorithms are based on the derived distributions and the Markov property of records, which also holds in the case when the initial observations are independent but non-identically distributed. At the end of this work, in Section 3, the proposed algorithms are tested by simulation experiments. In these experiments the records are generated for the case when the initial random variables have Gumbel distribution functions.

关键词： records Gumbel distribution function inverse-transform method rejection method generation algorithms elapsed time

来源：评论

学校读者我要写书评

暂无评论

Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions

引用

DISCRETE APPLIED MATHEMATICS 2008年第11期156卷 2020-2034页

作者： Khachiyan, Leonid Boros, Endre Elbassioni, Khaled Gurvich, Vladimir Max Planck Inst Informat D-66123 Saarbrucken Germany Rutgers State Univ RUTCOR Piscataway NJ 08854 USA

We consider monotone boolean OR, boolean AND-formulae phi of m atoms, each of which is a monotone inequality of the form f(i) (x) >= t(i) over the integers, where for i = 1..... m, f(i) : Z(n) bar right arrow R is a given monotone function and t(i) is a given threshold. We show that if the boolean OR-degree of phi is bounded by a constant, then for linear, transversal and polymatroid monotone inequalities all minimal integer vectors satisfying phi can be generated in incremental quasi-polynomial time. In contrast, the enumeration problem for the disjunction of m inequalities is NP-hard when m is part of the input. We also discuss some applications of the above results in disjunctive programming, data mining, matroid and reliability theory. (C) 2007 Elsevier B.V. All rights reserved.

关键词： dualization hypergraph transversals generation algorithms monotone systems of inequalities linear inequalities transversal inequalities polymatroid inequalities

来源：评论

学校读者我要写书评

暂无评论

On the complexity of monotone dualization and generating minimal hypergraph transversals

引用

DISCRETE APPLIED MATHEMATICS 2008年第11期156卷 2109-2123页

作者： Elbassioni, Khaled M. Max Planck Inst Informat D-66123 Saarbrucken Germany

In 1994 Fredman and Khachiyan established the remarkable result that the duality of a pair of monotone Boolean functions, in disjunctive normal forms, can be tested in quasi-polynomial time, thus putting the problem, most likely, somewhere between polynomiality and coNP-completeness. We strengthen this result by showing that the duality testing problem can in fact be solved in polylogarithmic time using a quasi-polynomial number of processors (in the PRAM model). While our decomposition technique can be thought of as a generalization of that of Fredman and Khachiyan, it yields stronger bounds on the sequential complexity of the problem in the case when the sizes of f and g are significantly different, and also allows for generating all minimal transversals of a given hypergraph using only polynomial space. (C) 2007 Elsevier B.V. All rights reserved.

关键词： dualization hypergraph transversals generation algorithms monotone Boolean functions polynomial space

来源：评论

学校读者我要写书评

暂无评论

COMPUTING MANY MAXIMAL INDEPENDENT SETS FOR HYPERGRAPHS IN PARALLEL

引用

PARALLEL PROCESSING LETTERS 2007年第2期17卷 141-152页

作者： Khachiyant, Leonid Boros, Endre Gurvich, Vladimir Elbassioni, Khaled Rutgers State Univ 640 Bartholomew Rd Piscataway NJ 08854 USA Max Planck Inst Informat D-66123 Saarbrucken Germany

A hypergraph H subset of 2(V) is called uniformly delta-sparse if for every nonempty subset X subset of V of vertices, the average degree of the sub-hypergraph of H induced by X is at most delta. We show that there is a deterministic algorithm that, given a uniformly delta-sparse hypergraph 1-L, and a positive integer k, outputs k or all minimal transversals for "H in O(delta log(l + k) polylog(delta vertical bar V vertical bar))-time using vertical bar V vertical bar(O(log delta)) k(O(delta)) processors. Equivalently, the algorithm can be used to compute in parallel k or all maximal independent sets for H.

关键词： Maximal independent sets minimal transversals generation algorithms hypergraphs global parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A Constant Amortized Time Algorithm for Generating Left-Child Sequences in Lexicographic Order 11th

A Constant Amortized Time Algorithm for Generating Left-Chil...

引用

11th International Frontiers of Algorithmics Workshop (FAW)

作者： Pai, Kung-Jui Chang, Jou-Ming Wu, Ro-Yu Ming Chi Univ Technol Dept Ind Engn & Management New Taipei Taiwan Natl Taipei Univ Business Inst Informat & Decis Sci Taipei Taiwan Lunghwa Univ Sci & Technol Dept Ind Management Taoyuan Taiwan

ISBN: (纸本)9783319596051;9783319596044

Wu et al. (Theoret. Comput. Sci. 556:25-33, 2014) recently introduced a new type of sequences, called left-child sequences (LC sequences for short), for representing binary trees. They pointed out that such sequences have a natural interpretation from the view point of data structure and gave a characterization of them. Based on this characterization, Pai et al. (International conference on combinatorial optimization and applications. Springer, Cham, pp. 505-518, 2016) showed that there is an easily implementing algorithm that uses generate-and test approach to filter all LC-sequences of binary trees with n internal nodes in lexicographic order, while in general this algorithm is not efficient at all. In this paper, we design two novel rotations that allow us to drastically alter the shape of binary trees (and thus their corresponding LC-sequences). As an application, these operations can be employed to generate all LC-sequences in lexicographic order. Accordingly, we present a more efficient algorithm associated with the new types of rotations for generating all LC-sequences and show that it takes only constant amortized running cost.

关键词： Constant amortized time algorithm Binary trees Left child sequences Lexicographic order generation algorithms Amortized cost

来源：评论

学校读者我要写书评

暂无评论

Simulation of records obtained from sequences of independent and non-identically distributed variables

引用

COMMUNICATIONS IN STATISTICS-SIMULATION AND COMPUTATION 2024年

作者： Stepanov, Alexei Immanuel Kant Balt Fed Univ Educ & Res Cluster Inst High Technol Kaliningrad Russia Immanuel Kant Balt Fed Univ Educ & Res Cluster Inst High Technol A Nevskogo 14 Kaliningrad 236041 Russia

In the present paper, we provide the density-mass functions of record times and values obtained from samples of independent and non-identically distributed random variables. By making use of these density-mass functions, we then present a record generation algorithm for the non-identical case. This algorithm was first proposed in the paper of S. A. Petukhov and A. V. Stepanov (2023) generation of records obtained from sequences of independent and non-identically distributed random variables. Vestnik St. Petersburg University, Mathematics 56 (4):540-8 in a more complicated form. The algorithm applies the Markovian property of records, which is known in the case when the initial observations are independent and identically distributed and which extends to the non-identical case. Later in the paper, we test the proposed algorithm by conducting simulation experiments with exponential and normal variables.

关键词： Records Exponential distribution generation algorithms Normal distribution 60 62

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：