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

A Computational Study of Physical Properties of the Smallest Fullerene, C₂₀ Nanoparticle

JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE 2013年第9期10卷 1908-1913页

作者： Khataee, H. R. Liew, A. W. C. Zhong, Y. Hanifehpour, Y. Joo, S. W. Griffith Univ Sch Informat & Commun Technol Nathan Qld 4222 Australia RMIT Univ Sch Aerosp Mech & Mfg Engn Bundoora Vic 3083 Australia Yeungnam Univ Sch Mech Engn WCU Nano Res Ctr Kyongsan 712749 South Korea

Computational nanotechnology provides theoretical understanding of complex nanoparticles properties and may enlighten their potential applications. In this paper, we use graph algorithms based on the dynamic programming to develop a software system which computes a set of optimal physical properties of the C-20 nanoparticle. The computational results of our developed software system have not been reported previously. C-20 nanoparticle is the smallest and simplest fullerene composed of twenty equivalent carbon atoms arranged in a cage structural form. The twenty carbon atoms of C-20 nanoparticle are also arranged in two other major structures: bowl and ring. The study considers all three major structures of C-20 nanoparticle and computes their physical indices including Wiener, hyper-Wiener, Harary and reciprocal Wiener. The Hosoya and hyper-Hosoya polynomials of the cage, bowl and ring structures of C-20 nanoparticle have been also computed. The accuracy of the computational results was proved with the mathematical equations between the indices and polynomials. Our computational results also showed good agreement with the physical properties of the cage, bowl and ring structures of C-20 nanoparticle.

关键词： C-20 Nanoparticle graph algorithms Computational Nanotechnology

来源：评论

学校读者我要写书评

暂无评论

Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs

引用

INFORMATION AND COMPUTATION 2013年 233卷 60-70页

作者： Dorn, Frederic Fomin, Fedor V. Lokshtanov, Daniel Raman, Venkatesh Saurabh, Saket SINTEF Energy Res Trondheim Norway Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India

In this paper we make the first step beyond bidimensionality by obtaining subexponential time algorithms for problems on directed graphs. We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied problems. For the first problem, k-LEAF OUT-BRANCHING, which is to find an oriented spanning tree with at least k leaves, we obtain an algorithm solving the problem in time 2(O(root k log k))n + n(O(1)) on directed graphs whose underlying undirected graph excludes some fixed graph H as a minor. For the special case when the input directed graph is planar, the running time can be improved to 2(O(root k))n + n(O(1)). The second example is a generalization of the DIRECTED HAMILTONIAN PATH problem, namely k-INTERNAL OUT-BRANCHING, which is to find all oriented spanning tree with at least k internal vertices. We obtain an algorithm solving the problem in time 2(O(root k log k)) + n(O(1)) on directed graphs whose underlying undirected graph excludes some fixed apex graph H as a minor. Finally, we observe that on these classes of graphs, the k-DIRECTED PATH problem is solvable in time O((1 + epsilon)(k)n(f(epsilon))), for any epsilon > 0, where f is some function of epsilon. Our methods are based on non-trivial combinations of obstruction theorems for undirected graphs, kernelization, problem-specific combinatorial structures, and a layering technique similar to the one employed by Baker to obtain PTAS for planar graphs. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Parameterized algorithms Subexponential running time Directed graph graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Better bounds for incremental frequency allocation in bipartite graphs

引用

THEORETICAL COMPUTER SCIENCE 2013年 514卷 75-83页

作者： Chrobak, Marek Jez, Lukasz Sgall, Jiri Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA Univ Wroclaw Inst Comp Sci PL-50383 Wroclaw Poland Acad Sci Czech Republic Inst Math CR-11567 Prague 1 Czech Republic Charles Univ Prague Fac Math & Phys Inst Comp Sci CZ-11800 Prague 1 Czech Republic

We study frequency allocation in wireless networks. A wireless network is modeled by an undirected graph, with vertices corresponding to cells. In each vertex, we have a certain number of requests, and each of those requests must be assigned a different frequency. Edges represent conflicts between cells, meaning that frequencies in adjacent vertices must be different as well. The objective is to minimize the total number of used frequencies. The offline version of the problem is known to be NP-hard. In the incremental version, requests for frequencies arrive over time and the algorithm is required to assign a frequency to a request as soon as it arrives. Competitive incremental algorithms have been studied for several classes of graphs. For paths, the optimal (asymptotic) ratio is known to be 4/3, while for hexagonal-cell graphs it is between 1.5 and 1.9126. For xi-colorable graphs, the ratio of (xi + 1)/2 can be achieved. In this paper, we prove nearly tight bounds on the asymptotic competitive ratio for bipartite graphs, showing that it is between 1.428 and 1.433. This improves the previous lower bound of 4/3 and upper bound of 1.5. Our proofs are based on reducing the incremental problem to a purely combinatorial (equivalent) problem of constructing set families with certain intersection properties. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Online algorithms Frequency allocation graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Maximum matching in multi-interface networks

引用

THEORETICAL COMPUTER SCIENCE 2013年 507卷 52-60页

作者： Kosowski, Adrian Navarra, Alfredo Pajak, Dominik Pinotti, Cristina M. Inria Bordeaux Sud Ouest F-33400 Talence France Univ Perugia Dipartimento Matemat & Informat I-06100 Perugia Italy

In heterogeneous networks, devices can communicate by means of multiple wireless interfaces. By choosing which interfaces to switch on at each device, several connections might be established. That is, the devices at the endpoints of each connection share at least one active interface. In this paper, we consider the standard matching problem in the context of multi-interface wireless networks. The aim is to maximize the number of parallel connections without incurring interferences. Given a network G = (V, E), nodes V represent the devices, and edges E represent the connections that can be established. If node x participates in the communication with one of its neighbors by means of interface i, then another neighboring node of x can establish a connection (but not with x) only if it makes use of interface j not equal i. The size of a solution for an instance of the outcoming matching problem, which we call Maximum Matching in Multi-Interface networks (MMMI for short), is always in between the sizes of the solutions for the same instance with respect to the standard matching and its induced version problems. However, we prove that MMMI is NP-hard even for proper interval graphs and for bipartite graphs of maximum degree Delta >= 3. We also show polynomially solvable cases of MMMI with respect to different assumptions. (C) 2013 Elsevier B.V. All rights reserved.

关键词： graph algorithms Induced matching problem Network optimization Wireless networks Multi-interface networks

来源：评论

学校读者我要写书评

暂无评论

How to Use Spanning Trees to Navigate in graphs

引用

ALGORITHMICA 2013年第3期66卷 479-511页

作者： Dragan, Feodor F. Xiang, Yang Kent State Univ Dept Comp Sci Algorithm Res Lab Kent OH 44242 USA Ohio State Univ Dept Biomed Informat Columbus OH 43210 USA

In this paper, we investigate three strategies of how to use a spanning tree T of a graph G to navigate in G, i.e., to move from a current vertex x towards a destination vertex y via a path that is close to optimal. In each strategy, each vertex v has full knowledge of its neighborhood N (G) [v] in G (or, k-neighborhood D (k) (v,G), where k is a small integer) and uses a small piece of global information from spanning tree T (e.g., distance or ancestry information in T), available locally at v, to navigate in G. We investigate advantages and limitations of these strategies on particular families of graphs such as graphs with locally connected spanning trees, graphs with bounded length of largest induced cycle, graphs with bounded tree-length, graphs with bounded hyperbolicity. For most of these families of graphs, the ancestry information from a Breadth-First-Search-tree guarantees short enough routing paths. In many cases, the obtained results are optimal up to a constant factor.

关键词： graph algorithms Navigating in graphs Spanning trees Routing in graphs Distances Ancestry k-Chordal graphs Tree-length lambda graphs delta-Hyperbolic graphs Lower bounds

来源：评论

学校读者我要写书评

暂无评论

On a facility location problem with applications to tele-diagnostic

引用

OPTIMIZATION LETTERS 2013年第6期7卷 1179-1192页

作者： Apollonio, N. Caramia, M. Italiano, G. F. Ist Applicaz Calcolo I-00185 Rome Italy Univ Roma Tor Vergata Dipartimento Ingn Impresa I-00133 Rome Italy Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy

Consider an undirected graph G modelling a network. Each vertex in the graph contains some physical devices, which can be monitored and possibly repaired from a remote site in case they become faulty. We assume that there can be two kinds of faults in the system: soft faults, which can be repaired remotely from another site (i.e., a monitor), and severe faults which cannot be repaired remotely and require further (possibly human) interventions. We assume that soft faults happen with some fixed probability lambda, 0 < lambda a parts per thousand currency sign 1. We investigate the problem of locating monitors in the network so as to minimize the total expected communication cost per fault. We formalize such a problem as a location problem with a cost function depending on lambda and study some properties of the optimal solutions. The latter are exploited for investigating the complexity of the problem and providing efficient approximation algorithms.

关键词： Algorithm complexity graph algorithms Location problems

来源：评论

学校读者我要写书评

暂无评论

Agglomerative clustering via maximum incremental path integral

引用

PATTERN RECOGNITION 2013年第11期46卷 3056-3065页

作者： Zhang, Wei Zhao, Deli Wang, Xiaogang Chinese Univ Hong Kong Dept Informat Engn Shatin Hong Kong Peoples R China Chinese Univ Hong Kong Dept Elect Engn Shatin Hong Kong Peoples R China

Agglomerative clustering, which iteratively merges small clusters, is commonly used for clustering because it is conceptually simple and produces a hierarchy of clusters. In this paper, we propose a novel graph-structural agglomerative clustering algorithm, where the graph encodes local structures of data. The idea is to define a structural descriptor of clusters on the graph and to assume that two clusters have large affinity if their structural descriptors undergo substantial change when merging them into one cluster. A key insight of this paper to treat a cluster as a dynamical system and its samples as states. Based on that, Path Integral, which has been introduced in statistical mechanics and quantum mechanics, is utilized to measure the stability of a dynamical system. It is proposed as the structural descriptor, and the affinity between two clusters is defined as Incremental Path Integral, which can be computed in a closed-form exact solution, with linear time complexity with respect to the maximum size of clusters. A probabilistic justification of the algorithm based on absorbing random walk is provided. Experimental comparison on toy data and imagery data shows that it achieves considerable improvement over the state-of-the-art clustering algorithms. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Agglomerative clustering Path integral graph algorithms Random walk

来源：评论

学校读者我要写书评

暂无评论

CiSE: A Circular Spring Embedder Layout Algorithm

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER graphICS 2013年第6期19卷 953-966页

作者： Dogrusoz, Ugur Belviranli, Mehmet E. Dilek, Alptug Bilkent Univ Dept Comp Engn TR-06800 Ankara Turkey Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92521 USA Sci & Technol Res Council Turkey TUBITAK BILGEM TR-06100 Ankara Turkey

We present a new algorithm for automatic layout of clustered graphs using a circular style. The algorithm tries to determine optimal location and orientation of individual clusters intrinsically within a modified spring embedder. Heuristics such as reversal of the order of nodes in a cluster and swap of neighboring node pairs in the same cluster are employed intermittently to further relax the spring embedder system, resulting in reduced inter-cluster edge crossings. Unlike other algorithms generating circular drawings, our algorithm does not require the quotient graph to be acyclic, nor does it sacrifice the edge crossing number of individual clusters to improve respective positioning of the clusters. Moreover, it reduces the total area required by a cluster by using the space inside the associated circle. Experimental results show that the execution time and quality of the produced drawings with respect to commonly accepted layout criteria are quite satisfactory, surpassing previous algorithms. The algorithm has also been successfully implemented and made publicly available as part of a compound and clustered graph editing and layout tool named CHISIO.

关键词： Information visualization visualization techniques and methodologies visualization systems and software graph algorithms algorithm design and analysis graph visualization graph drawing force-directed layout circular layout clustered graphs sequence alignment

来源：评论

学校读者我要写书评

暂无评论

SPLIT VERTEX DELETION meets VERTEX COVER: New fixed-parameter and exact exponential-time algorithms

引用

INFORMATION PROCESSING LETTERS 2013年第5-6期113卷 179-182页

作者： Cygan, Marek Pilipczuk, Marcin Univ Lugano IDSIA Lugano Switzerland Univ Warsaw Inst Informat PL-00325 Warsaw Poland

In the SPLIT VERTEX DELETION problem, given a graph G and an integer k, we ask whether one can delete k vertices from the graph G to obtain a split graph (i.e., a graph, whose vertex set can be partitioned into two sets: one inducing a clique and the second one inducing an independent set). In this paper we study exact (exponential-time) and fixed-parameter algorithms for SPLIT VERTEX DELETION. We show that, up to a factor quasipolynomial in k and polynomial in n, the SPLIT VERTEX DELETION problem can be solved in the same time as the well-studied VERTEX COVER problem. By plugging in the currently best fixed-parameter algorithm for VERTEX COVER due to Chen et al. [Theor. Comput Sci. 411 (40-42) (2010) 3736-3756], we obtain an algorithm that solves SPLIT VERTEX DELETION in time O(-1.2738(k)k(O(logk)) + n(3)). We show that all maximal induced split subgraphs of a given n-vertex graph can be listed in O(3(n/3) n(O(logn))) time. To achieve our goals, we prove the following structural result that may be of independent interest: for any graph G we may compute a family P of size n(O(logn)) containing partitions of V(C) into two parts, such that for any two disjoint sets X-C, X-I subset of V (G) where G[X-C] is a clique and G[X-I] is an independent set, there is a partition in P which contains all vertices of X-C on one side and all vertices of X-I on the other. Moreover, the family P can be enumerated in O(n(O(logn))) time. (C) 2013 Elsevier B.V. All rights reserved.

关键词： graph algorithms Fixed-parameter algorithms Split graphs Split vertex deletion Branching algorithm

来源：评论

学校读者我要写书评

暂无评论

Algorithmic aspect of stratified domination in graphs

引用

INFORMATION PROCESSING LETTERS 2013年第22-24期113卷 861-865页

作者： Chang, Gerard Jennhwa Chang, Chan-Wei Kuo, David Poon, Sheung-Hung Natl Taiwan Univ Dept Math Taipei 10617 Taiwan Natl Taiwan Univ Taida Inst Math Sci Taipei 10617 Taiwan Natl Ctr Theoret Sci Taipei Off Taipei Taiwan Natl Dong Hwa Univ Dept Appl Math Hualien 97401 Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30043 Taiwan

Chartrand, Haynes, Henning and Zhang introduced a variation of domination called stratified domination in graphs. This paper studies stratified domination from an algorithmic point of view. A 2-stratified (or black-white) graph is a graph in which every vertex is colored black or white. Given a black-white graph F rooted at a white vertex v, an F-coloring of a graph G = (V, E) is a black-white coloring of V for which every white vertex v of G belongs to a copy of F (not necessarily induced in G) rooted at v. An F-dominating set of G is the set of all black vertices in an F-coloring. The F-domination number gamma(F)(G) of G is the minimum cardinality of an F-dominating set. We consider the 3-vertex black-white graph F-3 rooted at a white vertex v adjacent to another white vertex u, which adjacent to a black vertex w. We prove that the F-3-domination problem is NP-complete for bipartite planar graphs and for chordal graphs. We also give a linear-time algorithm for the F-3-domination problem in trees. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Design of algorithms graph algorithms k-stratified graph Domination F-domination NP-complete Bipartite graph Planar graph Chordal graph Tree

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：