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

A Polynomial Delay algorithm for Enumerating 2-Edge-Connected Induced Subgraphs

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2022年第3期E105D卷 466-473页

作者： Ito, Taishu Sano, Yusuke Yamanaka, Katsuhisa Hirayama, Takashi Iwate Univ Morioka Iwate 0208551 Japan Iwate Univ Fac Sci & Engn Morioka Iwate 0208551 Japan

The problem of enumerating connected induced subgraphs of a given graph is classical and studied well. It is known that connected induced subgraphs can be enumerated in constant time for each subgraph. In this paper, we focus on highly connected induced subgraphs. The most major concept of connectivity on graphs is vertex connectivity. For vertex connectivity, some enumeration problem settings and enumeration algorithms have been proposed, such as k-vertex connected spanning subgraphs. In this paper, we focus on another major concept of graph connectivity, edge-connectivity. This is motivated by the problem of finding evacuation routes in road networks. In evacuation routes, edge-connectivity is important, since highly edge-connected subgraphs ensure multiple routes between two vertices. In this paper, we consider the problem of enumerating 2-edge-connected induced subgraphs of a given graph. We present an algorithm that enumerates 2-edge-connected induced subgraphs of an input graph G with n vertices and m edges. Our algorithm enumerates all the 2-edge-connected induced subgraphs in O(n(3)m vertical bar S-G vertical bar) time, where S-G is the set of the 2-edge-connected induced subgraphs of G. Moreover, by slightly modifying the algorithm, we have a O(n(3)m)-delay enumeration algorithm for 2-edge-connected induced subgraphs.

关键词： enumeration algorithm 2-edge-connected induced subgraph reverse search polynomial delay

来源：评论

学校读者我要写书评

暂无评论

Listing all the minimum spanning trees in an undirected graph

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2010年第14期87卷 3175-3185页

作者： Yamada, Takeo Kataoka, Seiji Watanabe, Kohtaro Natl Def Acad Dept Comp Sci Kanagawa 2398686 Japan

Efficient polynomial time algorithms are well known for the minimum spanning tree problem. However, given an undirected graph with integer edge weights, minimum spanning trees may not be unique. In this article, we present an algorithm that lists all the minimum spanning trees included in the graph. The computational complexity of the algorithm is O(N(mn+n2 log n)) in time and O(m) in space, where n, m and N stand for the number of nodes, edges and minimum spanning trees, respectively. Next, we explore some properties of cut-sets, and based on these we construct an improved algorithm, which runs in O(N m log n) time and O(m) space. These algorithms are implemented in C language, and some numerical experiments are conducted for planar as well as complete graphs with random edge weights.

关键词： minimum spanning tree enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Realistic roofs without local minimum edges over a rectilinear polygon

引用

THEORETICAL COMPUTER SCIENCE 2017年 675卷 15-26页

作者： Yoon, Sang Duk Ahn, Hee-Kap Sherette, Jessica POSTECH Dept Comp Sci & Engn Pohang South Korea Univ Texas San Antonio Dept Comp Sci San Antonio TX USA

Computing all possible roofs over a given ground plan is a common task in automatically reconstructing a three dimensional building. In 1995, Aichholzer et al. proposed a definition of a roof over a simple polygon P in the xy-plane as a terrain over P whose faces are supported by planes containing edges of P and making a dihedral angle pi/4 with the xy-plane. This definition, however, allows roofs with faces isolated from the boundary of P and local minimum edges inducing pools of rainwater. Very recently, Ahn et al. introduced "realistic roofs" over a rectilinear polygon with n vertices by imposing two additional constraints under which no isolated faces and no local minimum vertices are allowed. Their definition is, however, restricted and excludes a number of roofs with no local minimum edges. In this paper, we propose a new definition of realistic roofs over a rectilinear polygon that corresponds to the class of roofs without isolated faces and local minimum edges. We investigate the geometric and combinatorial properties of realistic roofs and show that the maximum possible number of distinct realistic roofs over a rectilinear n-gon is at most 1.3211(m) ((left perpendicular m/2 right perpendicular) (m)), where m = (n-4)/2. We also present two algorithms that generate all realistic roofs. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Realistic roof enumeration algorithm Computational geometry

来源：评论

学校读者我要写书评

暂无评论

BiMine+: An efficient algorithm for discovering relevant biclusters of DNA microarray data

引用

KNOWLEDGE-BASED SYSTEMS 2012年 35卷 224-234页

作者： Ayadi, Wassim Ellourni, Mourad Hao, Jin Kao Univ Tunis Higher Sch Sci & Technol Tunis LaTICE Tunis 1008 Tunisia Univ Angers LERIA F-49045 Angers France

Biclustering is a very useful tool for analyzing microarray data. It aims to identify maximal groups of genes which are coherent with maximal groups of conditions. In this paper, we propose a biclustering algorithm, called BiMine+, which is able to detect significant biclusters from gene expression data. The proposed algorithm is based on two original features. First, BiMine+ is based on the use of a new tree structure, called Modified Bicluster enumeration Tree (MBET), on which biclusters are represented by the profile shapes of genes. Second, BiMine+ uses a pruning rule to avoid both trivial biclusters and combinatorial explosion of the search tree. The performance of BiMine+ is assessed on both synthetic and real DNA microarray datasets. Experimental results show that BiMine+ competes favorably with several state-of-the-art biclustering algorithms and is able to extract functionally enriched and biologically relevant biclusters. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Biclustering Gene expression data Evaluation function enumeration algorithm Data mining

来源：评论

学校读者我要写书评

暂无评论

Realistic roofs over a rectilinear polygon

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2013年第9期46卷 1042-1055页

作者： Ahn, Hee-Kap Bae, Sang Won Knauer, Christian Lee, Mira Shin, Chan-Su Vigneron, Antoine POSTECH Dept Comp Sci & Engn Pohang South Korea Kyonggi Univ Dept Comp Sci Suwon South Korea Univ Bayreuth Inst Comp Sci D-95440 Bayreuth Germany Korea Adv Inst Sci & Technol Dept Comp Sci Taejon 305701 South Korea Hankuk Univ Foreign Studies Dept Digital & Informat Engn Yongin South Korea King Abdullah Univ Sci & Technol Geometr Modeling & Sci Visualizat Ctr Thuwal 239556900 Saudi Arabia

Given a simple rectilinear polygon P in the xy-plane, a roof over P is a terrain over P whose faces are supported by planes through edges of P that make a dihedral angle pi/4 with the xy-plane. According to this definition, some roofs may have faces isolated from the boundary of P or even local minima, which are undesirable for several practical reasons. In this paper, we introduce realistic roofs by imposing a few additional constraints. We investigate the geometric and combinatorial properties of realistic roofs and show that the straight skeleton induces a realistic roof with maximum height and volume. We also show that the maximum possible number of distinct realistic roofs over P is ((n-4)/2 left perpendicular(n-4)/4right perpendicular) when P has n vertices. We present an algorithm that enumerates a combinatorial representation of each such roof in O (1) time per roof without repetition, after O (n(4)) preprocessing time. We also present an O (n(5))-time algorithm for computing a realistic roof with minimum height or volume. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Realistic roof Straight skeleton Rectilinear polygon enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximal Quasi-Cliques Mining in Uncertain Graphs

引用

IEEE TRANSACTIONS ON BIG DATA 2023年第1期9卷 37-50页

作者： Qiao, Lianpeng Li, Rong-Hua Zhang, Zhiwei Yuan, Ye Wang, Guoren Qin, Hongchao Northeastern Univ Dept Comp Sci Shenyang 110004 Liaoning Peoples R China Beijing Inst Technol Dept Comp Sci Beijing 100081 Peoples R China

Cohesive subgraph mining is a fundamental problem in the field of graph data analysis. Many existing cohesive graph mining algorithms are mainly tailored to deterministic graphs. Real-world graphs, however, are often not deterministic, but uncertain in nature. Applications of such uncertain graphs include protein-protein interactions networks with experimentally inferred links and sensor networks with uncertain connectivity links. In this article, we study the problem of mining cohesive subgraphs from an uncertain graph. Specifically, we introduce a new (alpha,gamma)-quasi-clique model to model the cohesive subgraphs in an uncertain graph, and propose a basic enumeration algorithm to find all maximal (alpha,gamma)-quasi-cliques. We also develop an advanced enumeration algorithm based on several novel pruning rules, including early termination and candidate set reduction. To further improve the efficiency, we propose several optimization techniques. Extensive experiments on five real-world datasets demonstrate that our solutions are almost three times faster than the baseline approach.

关键词： Big Data Probability Heuristic algorithms Data mining Social networking Proteins Optimization Maximal(a,?)-quasi-clique uncertain graphs cohesive subgraphs enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2011年第2期E94D卷 211-219页

作者： Zhuang, Bingbing Nagamochi, Hiroshi Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Kyoto 6068501 Japan

In a rooted graph, a vertex is designated as its root. An outerplanar graph is represented by a plane embedding such that all vertices appear along its outer boundary. Two different plane embeddings of a rooted outerplanar graphs are called symmetric copies. Given integers n >= 3 and g >= 3, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted outerplanar graphs with exactly n vertices such that the size of each inner face is at most g without delivering two symmetric copies of the same graph.

关键词： enumeration algorithm graph algorithm planar graph outerplanar graph symmetry

来源：评论

学校读者我要写书评

暂无评论

On enumerating all minimal solutions of feedback problems

引用

DISCRETE APPLIED MATHEMATICS 2002年第1-3期117卷 253-265页

作者： Schwikowski, B Speckenmeyer, E Inst Syst Biol Seattle WA 98105 USA Inst Informat D-50969 Cologne Germany

We present an algorithm that generates all (inclusion-wise) minimal feedback vertex sets of a directed graph G = (V.E). The feedback vertex sets of G are generated with a polynomial delay of O(\V\(2)(\V\ + \E\)). We further show that the underlying technique can be tailored to generate all minimal solutions for the undirected case and the directed feedback arc set problem, both with a polynomial delay of O(\V\ \E\ (\V\ + \E\). Finally, we prove that computing the number of minimal feedback arc sets is #P-hard. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： feedback vertex sets feedback arc sets enumeration algorithm polynomial delay #P-hardness

来源：评论

学校读者我要写书评

暂无评论

algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties

引用

COMPUTERS & OPERATIONS RESEARCH 2017年 81卷 203-215页

作者： Rosa, Bruno Ferreira Freitas Souza, Marcone Jamilson de Souza, Sergio Ricardo de Franca Filho, Moacir Felizardo Ales, Zacharie Paul Michelon, Philippe Yves Fed Ctr Technol Educ Minas Gerais CEFET MG BR-30510000 Belo Horizonte MG Brazil Fed Univ Ouro Preto UFOP Dept Comp Sci BR-35400000 Ouro Preto MG Brazil Univ Avignon & Pays de Vaucluse LIA EA 4128 F-84911 Avignon France

This paper addresses the single machine scheduling problem with distinct time windows and sequence dependent setup times. The objective is to minimize the total weighted earliness and tardiness. The problem involves determining the job execution sequence and the starting time for each job in the sequence. An implicit enumeration algorithm denoted IE and a general variable neighborhood search algorithm denoted GVNS are proposed to determine the job scheduling. IE is an exact algorithm, whereas GVNS is a heuristic algorithm. In order to define the starting times, an O(n(2)) idle time insertion algorithm (ITIA) is proposed. IE and GVNS use the ITIA algorithm to determine the starting time for each job. However, the IE algorithm is only valid for instances with sequence -independent setup times, and takes advantage of theoretical results generated for this problem. Computational experiments show that the ITIA algorithm is more efficient than the only other equivalent algorithm found in the literature. The IE algorithm allows the optimal solutions of all instances with up to 15 jobs to be determined within a feasible computational time. For larger instances, GVNS produces better-quality solutions requiring less computational time compared with the other algorithm from the literature. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Scheduling Makespan Idle time enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

A hybrid algorithm for reliability evaluation of a multi-state system

引用

JOURNAL OF THE CHINESE INSTITUTE OF ENGINEERS 2013年第2期36卷 173-179页

作者： Xu, Xiu-Zhen Niu, Yi-Feng Henan Polytech Univ Sch Comp Sci & Technol Jiaozuo 454003 Peoples R China Henan Polytech Univ Sch Math & Informat Sci Jiaozuo 454003 Peoples R China

Multi-state two-terminal reliability for level d (MS2TR(d)) is one of the most important performance indices of a multi-state system. One common method for computing MS2TR(d) is using the multi-state minimal path (named d-MP). In this article, an efficient algorithm is presented to compute MS2TR(d) in terms of d-MPs. The main characteristics of the proposed algorithm include: (1) it requires neither minimal paths nor minimal cuts to be known;(2) it is a hybrid algorithm combining the max-flow method and the implicit enumeration method. Two examples are provided to illustrate the performance of the presented algorithm, and the computational results show that the hybrid algorithm is superior to the best-known method.

关键词： multi-state reliability d-flow d-MP enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：