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

Smallest Odd Holes in Claw-Free Graphs

35th International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Shrem, Shimon Stern, Michal Golumbic, Martin Charles Univ Haifa Caesarea Rothschild Inst IL-31999 Haifa Israel Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9783642114083

In this paper, we give general structure properties of a smallest odd hole in a claw-free graph that lead to a polynomial time algorithm. The algorithm is based on a modified BFS we call Gamma-BFS. For a graph G with n vertices and in edges, the time complexity of the algorithm is O(nm(2)). The algorithm is very easy to implement. We conclude the paper with a suggestion for an extension of our approach in order to detect an odd hole in a general graph.

关键词： claw-free graphs triangle-free graphs odd holes holes polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Establishment of survivable connections in WDM networks using partial path protection

Establishment of survivable connections in WDM networks usin...

引用

IEEE International Conference on Communications (ICC 2005)

作者： Xue, G Zhang, W Tang, J Thulasiraman, K Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85287 USA

ISBN: (纸本)0780389387

As a generalization of the traditional path protection scheme in WDM networks where a backup path is needed for each active path, the partial path protection scheme uses a collection of backup paths to protect an active path, where each backup path in the collection protects one or more links on the active path such that every link on the active path is protected by one of the backup paths. While there is no known polynomial time algorithm for computing an active path and a corresponding backup path using the path protection scheme for a given source-destination node pair, we show that an active path and a corresponding collection of backup paths using the partial path protection scheme can be computed in polynomial time, whenever they exist, under each of the following two network models: (a) dedicated protection in WDM networks without wavelength converters;and (b) shared protection in WDM networks without wavelength converters. Under each of the two models, we prove that for any given source s and destination d in the network, if one candidate active path connecting s and d is protectable using partial path protection, then any candidate active path connecting s and d is also protectable using partial path protection. This fundamental property leads to efficient shortest active path algorithms that can find an active path and its corresponding partial path protections whenever they exist. Simulation results show that shared partial path protection outperforms shared path protection in terms of blocking probability.

关键词： WDM networks backup multiplexing partial path protection polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Deterministic risk control for cost-effective network connections

Deterministic risk control for cost-effective network connec...

引用

3rd International Conference on Combinatorial Optimization and Applications (COCOA 2009)

作者： Alvarez-Miranda, Eduardo Chen, Xujin Hu, Jie Hu, Xiaodong Candia-Vejar, Alfredo Chinese Acad Sci Inst Appl Math Beijing 100190 Peoples R China Univ Talca Ind Management Dept Talca Chile Beijing Jiaotong Univ State Key Lab Rail Traff Control & Safety Beijing 100044 Peoples R China

This paper considers the minimum connection problem in networks with uncertain data. In such a network it is assumed that one can establish a link e by paying a cost c(e) in a given interval [c(e)(-), c(e)(+)] while taking a risk (c(e)(+) - c(e))/(c(e)(+) - c(e)(-)) of link failure. We develop polynomial time algorithms for minimum cost network connection with paths or spanning trees under risk-sum constraints. (C) 2009 Elsevier B.V. All rights reserved.

关键词： polynomial time algorithms Interval data Network design

来源：评论

学校读者我要写书评

暂无评论

Contracting chordal graphs and bipartite graphs to paths and trees

引用

Electronic Notes in Discrete Mathematics 2011年第C期37卷 87-92页

作者： Heggernes, Pinar Lévêque, Benjamin Christophe, Paul Department of Informatics University of Bergen Norway CNRS LIRMM Université Montpellier 2 France

Some of the most well studied problems in algorithmic graph theory deal with modifying a graph into an acyclic graph or into a path, using as few operations as possible. In Feedback Vertex Set and Longest Induced Path, the only allowed operation is vertex deletion, and in Spanning Tree and Longest Path, only edge deletions are permitted. We study the edge contraction variant of these problems: given a graph G and an integer k, decide whether G can be transformed into an acyclic graph or into a path using at most k edge contractions. Both problems are known to be NP-complete in general. We show that on chordal graphs these problems can be solved in O(n+m) and O(nm) time, respectively. On the negative side, both problems remain NP-complete when restricted to bipartite input graphs. © 2011 Elsevier B.V.

关键词： Chordal graphs Edge contractions polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

A linear time algorithm for computing 3-edge-connected components in a multigraph

引用

Japan Journal of Industrial and Applied Mathematics 1992年第2期9卷 163-180页

作者： Nagamochi, Hiroshi Ibaraki, Toshihide Department of Applied Mathematics and Physics Faculty of Engineering Kyoto University Kyoto 606 Japan

关键词： 3-edge-connected components edge-connectivity maximum flows minimum cuts polynomial time algorithms undirected multigraphs

来源：评论

学校读者我要写书评

暂无评论

Symbolic pointer analysis 02

Symbolic pointer analysis

引用

International Conference on Computer-Aided Design

作者： Zhu, JW Univ Toronto Dept Elect & Comp Engn Toronto ON M5S 3G4 Canada

ISBN: (纸本)0780376072

One of the bottlenecks in the recent movement of hardware synthesis from behavioral C programs is the difficulty in reasoning about runtime pointer values at compile time. The pointer analysis problem has been investigated in the compiler community for two decades, which has yielded efficient, polynomial time algorithms for context-insensitive analysis. However, at the accuracy level for which hardware synthesis is desired, namely context and flow sensitive analysis, the time and space complexity of the best algorithms reported grow exponentially with program size. In this paper, we present our first step towards a new analysis technology which potentially leads to almost-linear time complexity and sub-linear space complexity algorithm even for the most accurate analysis. The key idea that contributes to this efficiency is to implicitly encode the pointer-to relation in the Boolean domain, thereby capturing the procedure transfer function completely, compactly and canonically. This represents a wide departure from the traditional techniques, all of which explicitly capture pointer-to relation using variations of point-to graph, which have to be re-evaluated for different calling contexts. Experiments for our first flow-insensitive algorithm on common benchmarks show promising result.

关键词： hardware-software codesign integrated circuit design circuit CAD computational complexity Boolean functions program compilers symbolic pointer analysis hardware synthesis behavioral C programs runtime pointer values compile time polynomial time algorithms context-insensitive analysis context sensitive analysis flow sensitive analysis almost-linear time complexity sub-linear space complexity algorithm Boolean domain pointer-to relation encoding procedure transfer function point-to graph variations calling contexts flow-insensitive algorithm

来源：评论

学校读者我要写书评

暂无评论

Failure disjoint paths

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 1105-1112页

作者： Zotkiewicz, Mateusz Ben-Ameur, W. Pióro, Michał Institut TELECOM TELECOM SudParis Samovar CNRS UMR 5157 91011 Évry Cedex 9 rue Charles Fourier France Institute of Telecommunications Warsaw University of Technology 00-665 Warszawa Nowowiejska 15/19 Poland Institut TELECOM TELECOM SudParis Samovar CNRS UMR 5157 91011 Évry Cedex 9 rue Charles Fourier France Institute of Telecommunications Warsaw University of Technology 00-665 Warszawa Nowowiejska 15/19 Poland Department of Electrical and Information Technology Lund University S-221 00 Lund Sweden

Given a weighted directed graph where some arcs can fail while others are reliable, we aim to compute a shortest pair of failure-disjoint paths. If a reliable arc is used by both paths, its cost is counted only once. ... 详细信息

关键词： Disjoint paths polynomial time algorithms Shortest paths

来源：评论

学校读者我要写书评

暂无评论

Local and Global algorithms for Learning Dynamic Bayesian Networks

Local and Global Algorithms for Learning Dynamic Bayesian Ne...

引用

12th IEEE International Conference on Data Mining (ICDM)

作者： Nguyen Xuan Vinh Chetty, Madhu Coppel, Ross Wangikar, Pramod P. Monash Univ Fac Informat Technol Clayton Vic 3800 Australia Monash Univ Dept Microbiol Melbourne Vic Australia Indian Inst Technol Dept Chem Engn Bombay Maharashtra India

ISBN: (纸本)9781467346498;9780769549057

Learning optimal Bayesian networks (BN) from data is NP-hard in general. Nevertheless, certain BN classes with additional topological constraints, such as the dynamic BN (DBN) models, widely applied in specific fields such as systems biology, can be efficiently learned in polynomial time. Such algorithms have been developed for the Bayesian-Dirichlet (BD), Minimum Description Length (MDL), and Mutual Information Test (MIT) scoring metrics. The BD-based algorithm admits a large polynomial bound, hence it is impractical for even modestly sized networks. The MDL- and MIT-based algorithms admit much smaller bounds, but require a very restrictive assumption that all variables have the same cardinality, thus significantly limiting their applicability. In this paper, we first propose an improvement to the MDL- and MIT-based algorithms, dropping the equicardinality constraint, thus significantly enhancing their generality. We also explore local Markov blanket based algorithms for constructing BN in the context of DBN, and show an interesting result: under the faithfulness assumption, the mutual information test based local Markov blanket algorithms yield the same network as learned by the global optimization MIT-based algorithm. Experimental validation on small and large scale genetic networks demonstrates the effectiveness of our proposed approaches.

关键词： dynamic Bayesian network gene regulatory network global optimization polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Zumkeller Labeling algorithms for Complete Bipartite Graphs and Wheel Graphs

Zumkeller Labeling Algorithms for Complete Bipartite Graphs ...

引用

International Conference on Artificial Intelligence and Evolutionary algorithms in Engineering Systems (ICAEES)

作者： Balamurugan, B. J. Thirusangu, K. Thomas, D. G. Agni Coll Technol Thalambur Dept Math Madras 600130 Tamil Nadu India SIVET Coll Gowrivakkam Dept Math Madras 600073 Tamil Nadu India Madras Christian Coll Tambaram Dept Math Madras 600059 Tamil Nadu India

ISBN: (纸本)9788132221265;9788132221258

Let G = (V, E) be a graph. An injective function f: V -> N is said to be a Zumkeller labeling of the graph G, if the induced function f*: E -> N defined as f* (xy) = f(x)f(y) is a Zumkeller number for all xy is an element of E, x, y is an element of V. A graph G=(V, E) that admits a Zumkeller labeling is called a Zumkeller graph. In this paper, we provide polynomial time algorithms for Zumkeller labeling of complete bipartite graphs and wheel graphs.

关键词： polynomial time algorithms Zumkeller labeling Zumkeller numbers Complete bipartite graph Wheel graphs

来源：评论

学校读者我要写书评

暂无评论

Star Covers and Star Partitions of Cographs and Butterfly-free Graphs 10th

Star Covers and Star Partitions of Cographs and Butterfly-fr...

引用

10th International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Mondal, Joyashree Vijayakumar, S. Indian Inst Informat Technol Design & Mfg IIITDM Chennai 600127 India

ISBN: (纸本)9783031522123;9783031522130

A graph that is isomorphic to K-1,K- r for some r >= 0 is called a star. For a graph G = (V, E), any subset S of its vertex set V is called a star of G if the subgraph induced by S is a star. A collection C = {V-1, . . . , V-k} of stars in G is called a star cover of G if V-1 boolean OR. . . boolean OR V-k = V. A star cover C of G is called a star partition of G if it is also a partition of V. Given a graph G, the problem STAR COVER asks for a star cover of G of minimum size. Given a graph G, the problem STAR PARTITION asks for a STAR PARTITION of G of minimum size. Both the problems are NP-hard even for bipartite graphs [24]. In this paper, we obtain exact O(n(2)) time algorithms for both STAR COVER and STAR PARTITION on (C-4, P-4)-free graphs and on (2K(2), P-4)-free graphs. We also prove that STAR COVER and STAR PARTITION are polynomially equivalent, up to the optimum value, for butterfly-free graphs and present an O(n(14)) time O(log n)-approximation algorithm for these equivalent problems on butterfly-free graphs. We also obtain O(log n)-approximation algorithms for STAR COVER on hereditary graph classes.

关键词： Star Cover Star Partition Cographs Butterfly-free Graphs polynomial time algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：