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

44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Momege, Benjamin Inria Lille Nord Europe Villeneuve Dascq France

ISBN: (纸本)9783319731179;9783319731162

A graph with forbidden paths is a pair (G, F) where G is a graph and F is a subset of the set of paths in G. A simple path avoiding forbidden paths in (G, F) is a simple path in G such that each subpath is not in F. It is shown in [S. Szeider, Finding paths in graphs avoiding forbidden transitions, DAM 126] that the problem of deciding the existence of a simple path avoiding forbidden paths in a graph with forbidden paths is Np-complete even when the forbidden paths are restricted to be transitions, i.e., of length two. We give an exact exponential time algorithm that decides in O(2(n)n(2k+O(1))) time and O(n(k+O(1))) space whether there exists a simple path between two vertices of a given n-vertex graph where k is the length of the longest forbidden path. We also obtain an exact O(2(n) n(2k+O(1))) time and O(n(k+O(1))) space algorithm to check the existence of a Hamiltonian path avoiding forbidden paths and for the graphs with forbidden transitions an exact O * (2(n)) time and polynomial space algorithm to check the existence of a Hamiltonian cycle avoiding forbidden transitions. In the last section, we present a new sufficient condition for graphs to have a Hamiltonian cycle, which gives us some interesting corollaries for graphs with forbidden paths.

关键词： Exponential time algorithms exact algorithms Graph algorithms Forbidden paths Hamiltonian cycles

来源：评论

学校读者我要写书评

暂无评论

Fast and practical algorithms for planted (l, d) motif search

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2007年第4期4卷 544-552页

作者： Davila, Jaime Balla, Sudha Rajasekaran, Sanguthevar Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA

We consider the planted (l,d) motif search problem, which consists of finding a substring of length l that occurs in a set of input sequences {s(1),...,s(n)} with up to d errors, a problem that arises from the need to find transcription factor-binding sites in genomic information. We propose a sequence of practical algorithms, which start based on the ideas considered in PMS1. These algorithms are exact, have little space requirements, and are able to tackle challenging instances with bigger d, taking less time in the instances reported solved by exact algorithms. In particular, one of the proposed algorithms, PMSprune, is able to solve the challenging instances, such as (17, 6) and (19, 7), which were not previously reported as solved in the literature.

关键词： planted motif search problem challenging instances exact algorithms branch and bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast Polynomial-Space algorithms Using Inclusion-Exclusion

引用

ALGORITHMICA 2013年第4期65卷 868-884页

作者： Nederlof, Jesper Univ Bergen Dept Informat N-5020 Bergen Norway

Given a graph with n vertices, k terminals and positive integer weights not larger than c, we compute a minimum Steiner Tree in time and space, where the notation omits terms bounded by a polynomial in the input-size. We obtain the result by defining a generalization of walks, called branching walks, and combining it with the Inclusion-Exclusion technique. Using this combination we also give -time polynomial space algorithms for Degree Constrained Spanning Tree, Maximum Internal Spanning Tree and #Spanning Forest with a given number of components. Furthermore, using related techniques, we also present new polynomial space algorithms for computing the Cover Polynomial of a graph, Convex Tree Coloring and counting the number of perfect matchings of a graph.

关键词： Inclusion-Exclusion Fixed parameter tractability exact algorithms Polynomial space Steiner tree

来源：评论

学校读者我要写书评

暂无评论

2-Interconnected facility location: Specification, complexity, and exact solutions

引用

Electronic Notes in Discrete Mathematics 2013年 41卷 21-28页

作者： Chimani, Markus Kandyba, Maria Martens, Maren Faculty of Mathematics and Computer Science Uni Jena Germany

Connected facility location combines cost-efficient facility placement and the requirement to connect the facilities among each other. Such problems arise, e.g., in telecommunication applications where networks consist of a central core and local clients connected to it. Reliability of the core is a central issue, and we may hence require the core to be at least *** establish the problem class of 2-interConnected Facility Location (2-iCFL), categorize its central variants, and prove that they are hard to approximate. However, our computational results show that our orientation-based ILPs allow us to effectively solve such problems to optimality for hundreds of nodes. We also establish constructive characterizations for feasible problem instances, to be used for algorithmic feasibility checks, preprocessing, and heuristics. © 2013 Elsevier B.V.

关键词： 2-connectivity exact algorithms Experiments Facility location Inapproximability Integer programming

来源：评论

学校读者我要写书评

暂无评论

algorithms for DNA Sequencing by Hybridization: A Review

Algorithms for DNA Sequencing by Hybridization: A Review

引用

3rd International Conference on Bioinformatics and Biomedical Engineering

作者： Xie, Hongwei Yuan, Qianqian Liao, Ling Taiyuan Univ Technol Coll Comp & Software Engn Taiyuan 030024 Shanxi Peoples R China

ISBN: (纸本)9781424429011

One of the most challenging problems in computational biology is the reconstruction of DNA sequences from DNA fragments. This paper describes the problems of sequencing by hybridization with standard, isothermic and multistage oligonucleotide libraries. However, the problems are NP-hard in the strong sense in case of errors. With the study of combinatorial optimization, it has become common for the researchers to apply the exact and heuristic algorithms, especially the latter, to solve these problems. Though there have been various available methods in the literature, researchers still have difficulties in choosing the best method that could solve these problems well. This paper aims to review the existing algorithms, compare them, point out the flaws of these works and indicate the emerging trend.

关键词： Sequencing by hybridization Standard libraries Isothermic libraries Multistage libraries exact algorithms Heuristics

来源：评论

学校读者我要写书评

暂无评论

Efficient Production Scheduling by Exploiting Repetitive Product Configurations 21

Efficient Production Scheduling by Exploiting Repetitive Pro...

引用

IEEE 21st International Conference on Industrial Informatics (INDIN)

作者： Gruettemeier, Niels Balzereit, Kaja Soni, Nehal Bunte, Andreas Fraunhofer IOSB INA Lemgo Germany

ISBN: (纸本)9781665493130

We consider the problem of scheduling production jobs on a single machine with sequence dependent family setup times and individual job deadlines. Given a set of jobs, the goal is to minimize the total time to process all jobs while every job meets its deadline. We study algorithms that compute an exact solution to the problem. Motivated by one example use case, we exploit a natural structural observation that occurs in many production settings: the number of product configurations may be significantly smaller than the total number of jobs. We identify an algorithm that is efficient in this setting in terms of performance. We experimentally evaluate its running time and compare it with two other natural approaches of exact job scheduling.

关键词： scheduling NP-hard problem exact algorithms experimental evaluation

来源：评论

学校读者我要写书评

暂无评论

Determinant Sums for Undirected Hamiltonicity

Determinant Sums for Undirected Hamiltonicity

引用

IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)

作者： Bjorklund, Andreas Lund Univ Dept Comp Sci S-22100 Lund Sweden

ISBN: (纸本)9780769542447

We present a Monte Carlo algorithm for Hamiltonicity detection in an n-vertex undirected graph running in O*(1.657(n)) time. To the best of our knowledge, this is the first superpolynomial improvement on the worst case runtime for the problem since the O*(2(n)) bound established for TSP almost fifty years ago (Bellman 1962, Held and Karp 1962). It answers in part the first open problem in Woeginger's 2003 survey on exact algorithms for NP-hard problems. For bipartite graphs, we improve the bound to O*(1.414(n)) time. Both the bipartite and the general algorithm can be implemented to use space polynomial in n. We combine several recently resurrected ideas to get the results. Our main technical contribution is a new reduction inspired by the algebraic sieving method for k-Path (Koutis ICALP 2008, Williams IPL 2009). We introduce the Labeled Cycle Cover Sum in which we are set to count weighted arc labeled cycle covers over a finite field of characteristic two. We reduce Hamiltonicity to Labeled Cycle Cover Sum and apply the determinant summation technique for exact Set Covers (Bjorklund STACS 2010) to evaluate it.

关键词： exact algorithms Hamiltonicity Monte Carlo algorithm Monte Carlo methods NP-hard problem TSP algebraic sieving method bipartite graphs determinant summation exact set cover graph theory graphs labeled cycle cover sum optimisation space polynomial undirected Hamiltonicity detection undirected graph worst case runtime

来源：评论

学校读者我要写书评

暂无评论

Shortest color-spanning intervals

引用

20th International Conference on Computing and Combinatorics (COCOON)

作者： Jiang, Minghui Wang, Haitao Utah State Univ Dept Comp Sci Logan UT 84322 USA

Given a set of n points on a line, where each point has one of k colors, and given an integer si >= 1 for each color i, 1 = 1. We also obtain some interesting results for the general problem SCSI-t. From the negati... 详细信息

ISBN: (纸本)9783319087825

Given a set of n points on a line, where each point has one of k colors, and given an integer si >= 1 for each color i, 1 <= i <= k, the problem SHORTEST COLOR-SPANNING t INTERVALS (SCSI-t) aims at finding t intervals to cover at least si points of each color i, such that the maximum length of the intervals is minimized. Chen and Misiolek introduced the problem SCSI-1, and presented an algorithm running in O(n) time if the input points are sorted. Khanteimouri et al. gave an O (n(2) logn) time algorithm for the special case of SCSI-2 with s(i) = 1 for all colors i. In this paper, we present an improved algorithm with running time of 0(n2) for SCSI-2 with arbitrary si >= 1. We also obtain some interesting results for the general problem SCSI-t. From the negative direction, we show that approximating SCSI-t within any ratio is NP-hard when t is part of the input, is W[2]-hard when t is the parameter, and is W[1]-hard with both t and k as parameters. Moreover, the NP-hardness and the W[2]-hardness with parameter t hold even if si = 1 for all i. From the positive direction, we show that SCSI-t with si = 1 for all i is fixed-parameter tractable with k as the parameter, and admits an exact algorithm running in 0 (2(k)n . max{k, logn}) time. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Color-spanning objects Computational geometry exact algorithms Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Finding a Dense Subgraph with Sparse Cut 18

Finding a Dense Subgraph with Sparse Cut

引用

27th ACM International Conference on Information and Knowledge Management (CIKM)

作者： Miyauchi, Atsushi Kakimura, Naonori RIKEN AIP Tokyo Japan Keio Univ Yokohama Kanagawa Japan

ISBN: (纸本)9781450360142

Community detection is one of the fundamental tasks in graph mining, which has many real-world applications in diverse domains. In this study, we propose an optimization model for finding a community that is densely connected internally but sparsely connected to the rest of the graph. The model extends the densest subgraph problem, in which we maximize the density while minimizing the average cut size. We first show that our proposed model can be solved efficiently. Then we design two polynomial-time exact algorithms based on linear programming and a maximum flow algorithm, respectively. Moreover, to deal with larger-sized graphs in practice, we present a scalable greedy algorithm that runs in almost linear time with theoretical performance guarantee of the output. In addition, as our model is closely related to a quality function called the modularity density, we show that our algorithms can also be used to find global community structure in a graph. With thorough experiments using well-known real-world graphs, we demonstrate that our algorithms are highly effective in finding a suitable community in a graph. For example, for web-Google, our algorithm finds a solution with more than 99.1% density and less than 3.1% cut size, compared with a solution obtained by a baseline algorithm for the densest subgraph problem.

关键词： Graphs community detection densest subgraph sparsest cut modularity density exact algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Association Rules Mining exact, Approximate and Parallel Methods: A Survey

引用

SN Computer Science 2021年第6期2卷 449页

作者： Hamdad, Leila Benatchba, Karima Laboratory LCSI Ecole Nationale Supérieure en Informatique (ESI) Alger Algeria Laboratory LMCS Ecole Nationale Supérieure en Informatique (ESI) Alger Algeria

Association rules mining (ARM) is an unsupervised learning task. It is used to generate significant and relevant association rules among items in a database. APRIORI and FP-GROWTH are the most popular and used algorithms nowadays for extracting such rules. They are exact methods that consist of two phases. First, frequent itemsets are generated. Then, the latter are used to generate rules. The main drawback of both algorithms is their high execution time. To overcome this drawback, metaheuristics have been proposed. Moreover, to optimize the execution time, since the amount of data is in continuous growth, some parallel architectures can be found in the literature. In this paper, we present an overview of existing literature that investigate the ARM problem using both metaheuristics and parallelism. We will focus on the recent algorithms that tackle these problems using approximate methods and GPU. We will present a non-exhaustive classification of different algorithms according to the type of execution (sequential or parallel) and type of method (exact or approximate). © 2021, Springer. All rights reserved.

关键词： Association rules CPU Data mining exact algorithms GPU Metaheuristics Parallel

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：