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

All-pairs shortest paths with real weights in O(n³/logn) time

ALGORITHMICA 2008年第2期50卷 236-243页

作者： Chan, Timothy M. Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

We describe an O(n(3)/logn)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (SIAM J. Comput. 5:49-60, 1976), Takaoka (Inform. Process. Lett. 43:195-199, 1992), Dobosiewicz (Int. J. Comput. Math. 32:49-60, 1990), Han (Inform. Process. Lett. 91:245-250, 2004), Takaoka (Proc. 10th Int. Conf. Comput. Comb., Lect. Notes Comput. Sci., vol. 3106, pp. 278-289, Springer, 2004), and Zwick (Proc. 15th Int. Sympos. algorithms and Computation, Lect. Notes Comput. Sci., vol. 3341, pp. 921-932, Springer, 2004). The new algorithm is surprisingly simple and different from previous ones.

关键词： shortest paths graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Innovative computational methods for transcriptomic data analysis: A case study in the use of FPT for practical algorithm design and implementation

引用

COMPUTER JOURNAL 2008年第1期51卷 26-38页

作者： Langston, Michael A. Perkins, Andy D. Saxton, Arnold M. Scharff, Jon A. Voy, Brynn H. Univ Tennessee Dept Comp Sci Knoxville TN 37996 USA Univ Tennessee Dept Anim Sci Knoxville TN 37996 USA Oak Ridge Natl Lab Oak Ridge TN 37831 USA

Tools of molecular biology and the evolving tools of genomics can now be exploited to study the genetic regulatory mechanisms that control cellular responses to a wide variety of stimuli. These responses are highly complex, and involve many genes and gene products. The main objectives of this paper are to describe a novel research program centered on understanding these responses by ( i) developing powerful graph algorithms that exploit the innovative principles of fixed parameter tractability in order to generate distilled gene sets;( ii) producing scalable, high performance parallel and distributed implementations of these algorithms utilizing cutting-edge computing platforms and auxiliary resources;( iii) employing these implementations to identify gene sets suggestive of co-regulation;and ( iv) performing sequence analysis and genomic data mining to examine, winnow and highlight the most promising gene sets for more detailed investigation. As a case study, we describe our work aimed at elucidating genetic regulatory mechanisms that control cellular responses to low-dose ionizing radiation ( IR). A low-dose exposure, as defined here, is an exposure of at most 10 cGy ( rads). While the consequences of high doses of radiation are well known, the net outcome of low-dose exposures continues to be debated, with support in the literature for both detrimental and beneficial effects. We use genome-scale gene expression data collected in response to low-dose IR exposure in vivo to identify the pathways that are activated or repressed as a tissue responds to the radiation insult. The driving motivation is that knowledge of these pathways will help clarify and interpret physiological responses to IR, which will advance our understanding of the health consequences of low-dose radiation exposures.

关键词： transcriptomic data analysis fixed-parameter tractability graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Hamiltonicity of simplicial-connected graphs:: an algorithm based on clique decomposition

Hamiltonicity of simplicial-connected graphs:: an algorithm ...

引用

5th International Conference on Information Technology - New Generations

作者： Vallee, Thierry Bretto, Alain Georgia Southern Univ Dept Math Sci Statesboro GA 30458 USA Univ Caen GREYC UMR 6072 F-14032 Caen France

ISBN: (纸本)9780769530994

An important property of graph which concerns their applications to networks is Hamiltonicity. Determining if a graph is hamiltonian is a NP-complete problem and no satisfactory characterization exists. Nevertheless, many sufficient conditions were found, usually expressed in terms of degree, connectivity, density, toughness, independent set, regularity and forbidden subgraphs. In 1973, Goodman and Hedetniemi gave two alternative sufficient conditions uniquely based on the possibility to decompose in some ways the graph into cliques. We first generalise one of these two conditions. We give a new clique decomposition condition which proves the hamiltonicity of a broader class of graphs. Then, we present a polynomial algorithm which decides the existence of such a decomposition for simplicial-connected graphs. A graph is simplicial-connected if every vertex is connected by a walk to a simplicial one(1). In particular, each connected graph containing a simplicial vertex is simplicial-connected, and so is every chordal graph.

关键词： network Hamiltonicity graph theory graph algorithms clique covering

来源：评论

学校读者我要写书评

暂无评论

The polynomial dichotomy for three nonempty part sandwich problems

引用

Electronic Notes in Discrete Mathematics 2008年第C期30卷 81-86页

作者： Teixeira, Rafael B. Dantas, Simone de Figueiredo, Celina M.H. COPPE Universidade Federal do Rio de Janeiro Brazil Instituto de Matemática Universidade Federal Fluminense Brazil

关键词： Computational complexity graph algorithms Structural characterization of graphs

来源：评论

学校读者我要写书评

暂无评论

Computing branch decomposition of large planar graphs

引用

7th International Workshop on Experimental algorithms

作者： Bian, Zhengbing Gu, Qian-Ping Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

ISBN: (纸本)9783540685487

A graph of small branchwidth admits efficient dynamic programming algorithms for many NP-hard problems on the graph. A key step in these algorithms is to find a branch decomposition of small width for the graph. Given a planar graph G of n vertices, an optimal branch decomposition of G can be computed in polynomial time, e.g., by the edge-contraction method in O(n(3)) time. All known algorithms for the planar branch decomposition use Seymour and Thomas procedure which, given an integer beta, decides whether G has the branchwidth at least beta or not in O(n(2)) time. Recent studies report efficient implementations of Seymour and Thomas procedure that compute the branchwidth of planar graphs of size up to one hundred thousand edges in a practical time and memory space. Using the efficient implementations as a subroutine, it is reported that the edge-contraction method computes an optimal branch decomposition for planar graphs of size up to several thousands edges in a practical time but it is still time consuming for graphs with larger size. In this paper, we propose divide-and-conquer based algorithms of using Seymour and Thomas procedure to compute optimal branch decompositions of planar graphs. Our algorithms have time complexity O(n(3)). Computational studies show that our algorithms are much faster than the edge-contraction algorithms and can compute an optimal branch decomposition of some planar graphs of size up to 50,000 edges in a practical time.

关键词： graph algorithms branch-decomposition planar graphs algorithm engineering computational study

来源：评论

学校读者我要写书评

暂无评论

Method and software tool for an optimized passenger orientated connection management

Method and software tool for an optimized passenger orientat...

引用

11th International Conference on Computer System Design and Operation in the Railway and other Transit Systems

作者： Klemenz, M. Radtke, A. Leibniz Univ Hannover Inst Transport Railway Construct & Operat Hannover Germany

ISBN: (纸本)9781845641269

The trust of the customers in adherence to their expectation to a transport service determines the modal split of the passenger transport. Therefore it has to be a goal for each public transport operation company to maintain and to improve the customer's trust. An important service criteria by a customer accepted public transport offer is the travel time. The travel time depends on the running time, the dwell time, etc., but also on the number of transfer procedures and the transfer waiting time. One of the essential research problems in the surroundings of the connection planning is the question under which condition it is appropriate for the planning of a connection. An important aspect to answer this question is the evaluation of the additional total travel time for all involved passengers in consideration of an achieved (additional travel time for transit passengers in the connecting vehicle) or not achieved (additional travel time for transfer passengers in the feeder vehicle) connection. The paper develops a new method of an optimized passenger orientated connection management during the planning process (scheduled timetable). The goal is to minimize the additional travel time in consideration of a planned or not planned connection based on the number of all involved passengers. At first it is necessary to identify all influencing variables. After that all boundary conditions will be modelled by using the graph theory. With an adequate shortest path algorithm it is possible to generate connection strategies specific for stations, lines or the whole networks. Particularities of railway operation (e. g. turn around times, operating fleet, timetable interval, conflicts, infrastructure bottlenecks) also can been considered in the model. For the practical use was developed the software tool ANPLA which is helpful for operating companies or for the timetable construction to solve the set of problems in the surroundings of the connection management. Furthermore the p

关键词： connection management timetable construction transit and transfer passenger graph algorithms minimized travel time

来源：评论

学校读者我要写书评

暂无评论

Empirical Study on Branchwidth and Branch Decomposition of Planar graphs

引用

10th Workshop on Algorithm Engineering and Experiments/5th Workshop on Analytic Algorithmics and Combinatorics

作者： Bian, Zhengbing Gu, Qian-Ping Marzban, Marjan Tamaki, Hisao Yoshitake, Yumi Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Meiji Univ Dept Comp Sci Kawasaki Kanagawa 2148571 Japan

ISBN: (纸本)9780898716535

We propose efficient implementations of Seymour and Thomas algorithm which, given a planar graph and an integer beta, decides whether the graph has the branchwidth at least beta. The computational results of our implementations show that the branchwidth of a planar graph can be computed in a practical time and memory space for some instances of size about one hundred thousand edges. Previous studies report that a straightforward implementation of the algorithm is memory consuming, which could be a bottleneck for solving instances with more than a few thousands edges. Our results suggest that with efficient implementations, the memory space required by the algorithm may not be a bottleneck in practice. Applying our implementations, an optimal branch decomposition of a planar graph of practical size can be computed in a reasonable time. Branch-decomposition based algorithms have been explored as an approach for solving many NP-hard problems on graphs. The results of this paper suggest that the approach could be practical.

关键词： graph algorithms branch-decomposition planar graphs algorithm engineering computational study

来源：评论

学校读者我要写书评

暂无评论

Perturb+Mutate: Semisynthetic Circuit Generation for Incremental Placement and Routing

引用

ACM Transactions on Reconfigurable Technology and Systems 2008年第3期1卷 1-24页

作者： Grant, David Lemieux, Guy Department of Electrical and Computer Engineering The University of British Columbia Vancouver 2332 Main Mall V6T 1Z4 Canada

CAD tool designers are always searching for more benchmark circuits to stress their software. In this article we present a heuristic method to generate benchmark circuits specially suited for incremental place-and-route tools. The method removes part of a real circuit and replaces it with an altered version of the same circuit to mimic an incremental design change. The alteration consists of two steps: mutate followed by perturb. The perturb step exactly preserves as many circuit characteristics as *** perturbing, reproduction of interconnect locality, a characteristic that is difficult to measure reliably or reproduce exactly, is controlled using a new technique, ancestor depth control (ADC). Perturbing with ADC produces circuits with postrouting properties that match the best techniques known to-date. The mutate step produces targetted mutations resulting in controlled changes to specific circuit properties (while keeping other properties constant). We demonstrate one targetted mutation heuristic, scale, to significantly change circuit size with little change to other circuit characteristics. The method is simple enough for inclusion in a CAD tool directly, and fast enough for use in on-the-fly benchmark generation. © 2008, ACM. All rights reserved.

关键词： algorithms Automated development tools Design design automation Experimentation graph algorithms hardware-supporting software Measurement place and route Reliability testing Verification

来源：评论

学校读者我要写书评

暂无评论

Finding Strongly Connected Components in Parallel using O(log² n) Reachability Queries 08

Finding Strongly Connected Components in Parallel using <i>O...

引用

20th ACM Symposium on Parallelism in algorithms and Architectures

作者： Schudy, Warren Brown Univ Providence RI 02912 USA

ISBN: (纸本)9781595939739

We give a randomized (Las-Vegas) parallel algorithm for computing strongly connected components of a graph with n vertices and m edges. The runtime is dominated by O(log(2) n) multi-source parallel reachability queries;i.e. O(log(2) n) calls to a subroutine that computes the union of the descendants of a given set of vertices in a given digraph. Our algorithm also topologically sorts the strongly connected components. Using Ullman and Yannakakis's [22] techniques for the reachability subroutine gives our algorithm runtime (O) over tilde (t) using mn/t(2) processors for any (n(2)/m)(1/3) <= t <= n. On sparse graphs, this improves the number of processors needed to compute strongly connected components and topological sort within time n(1/3) <= t <= n from the previously best known (n/t)(3) [20] to (n/t)(2).

关键词： graph algorithms Parallel algorithms Strongly connected components Topological sort Transitive closure bottleneck

来源：评论

学校读者我要写书评

暂无评论

Every Minor-Closed Property of Sparse graphs is Testable

Every Minor-Closed Property of Sparse Graphs is Testable

引用

14th Annual ACM International Symposium on Theory of Computing

作者： Benjamini, Itai Schramm, Oded Shapira, Asaf Microsoft Res Redmond WA USA

ISBN: (纸本)9781605580470

Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph C of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P and the case that one should add/remove at least epsilon dn edges of G to make it satisfy P. In sharp contrast;to property testing of dense graphs, which is relatively well understood, very few properties are known to be testable in bounded degree graphs with a constant number of queries. In this paper we identify for the first time a large (and natural) family of properties that can be efficiently tested in bounded degree graphs, by showing that every minor-closed graph property can be tested with a, constant, number of queries. As a special case, we infer that many well studied graph properties, like being planar, outer-planar, series-parallel, bounded genus, bounded tree-width and several others, are testable with a constant number of queries. None of these properties was previously known to be testable even with o(n) queries. The proof combines results from the theory of graph minors with results on convergent sequences of sparse graphs, which rely on martingale arguments.

关键词： Property Testing graph algorithms Minor Closed Properties

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：