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

Constant Time Enumeration of Subtrees with Exactly k Nodes in a Tree

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2014年第3期E97D卷 421-430页

作者： Wasa, Kunihiro Kaneta, Yusaku Uno, Takeaki Arimura, Hiroki Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Hokkaido 0600814 Japan Natl Inst Informat Tokyo 1018430 Japan

By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the k-subtree enumeration problem with a tree of n nodes as an input graph, which is originally introduced by (Ferreira, Grossi, and Rizzi, ESA' 11, 275-286, 2011) for general graphs. Based on reverse search technique (Avis and Fukuda, Discrete Appl. Math., vol.65, pp.21-46, 1996), we present the first constant delay enumeration algorithm that lists all k-subtrees of an input rooted tree in O(1) worst-case time per subtree. This result improves on the straightforward application of Ferreira et al's algorithm with O(k) amortized time per subtree when an input is restricted to tree. Finally, we discuss an application of our algorithm to a modification of the graph motif problem for trees.

关键词： graph algorithm enumeration algorithm constant delay enumeration motif discovery tree mining

来源：评论

学校读者我要写书评

暂无评论

Complexity of the multi-service center problem

引用

THEORETICAL COMPUTER SCIENCE 2020年 842卷 18-27页

作者： Ito, Takehiro Kakimura, Naonori Kobayashi, Yusuke Tohoku Univ Sendai Miyagi Japan Keio Univ Tokyo Japan Kyoto Univ Kyoto Japan

The multi-service center problem is a variant of facility location problems. In the problem, we consider locating p facilities on a graph, each of which provides distinct service required by all vertices. Each vertex incurs the cost determined by the sum of the weighted distances to the p facilities. The aim of the problem is to minimize the maximum cost among all vertices. This problem is known to be NP-hard for general graphs, while it is solvable in polynomial time when p is a fixed constant. In this paper, we give sharp analyses for the complexity of the problem from the viewpoint of graph classes and weights on vertices. We first propose a polynomial-time algorithm for trees when p is a part of input. In contrast, we prove that the problem becomes strongly NP-hard even for cycles. We also show that when vertices are allowed to have negative weights, the problem becomes NP-hard for paths of only three vertices and strongly NP-hard for stars. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Facility location graph algorithm Multi-service location

来源：评论

学校读者我要写书评

暂无评论

Irregularity Strength of Circulant graphs Using algorithmic Approach

引用

IEEE ACCESS 2021年 9卷 54401-54406页

作者： Asim, Muhammad Ahsan Hasni, Roslan Ahmad, Ali Assiri, Basem Semanicova-Fenovcikova, Andrea Jazan Univ Coll Comp Sci & Informat Technol Jazan 82727 Saudi Arabia Univ Malaysia Terengganu Sch Informat & Appl Math Kuala Terengganu 21030 Malaysia Tech Univ Dept Appl Math & Informat Kosice 04001 Slovakia

This paper deals with decomposition of complete graphs on n vertices into circulant graphs with reduced degree r < n - 1. They are denoted as C-n(a(1), a(2), ... , a(m)), where a(1) to a(m) are generators. Mathematical labeling for such bigger (higher order and huge size) and complex (strictly regular with so many triangles) graphs is very difficult. That is why after decomposition, an edge irregular k-labeling for these subgraphs is computed with the help of algorithmic approach. Results of k are computed by implementing this iterative algorithm in computer. Using the values of k, an upper bound for edge irregularity strength is suggested for C-n(a(1), a(2), ... , a(m)) that is vertical bar E vertical bar/2 log(2) vertical bar V vertical bar.

关键词： Upper bound Labeling Topology Network topology Licenses Generators Program processors Edge irregular labeling circulant graph graph algorithm computational complexity Sidon sequence

来源：评论

学校读者我要写书评

暂无评论

Finding a Friendly Community in Social Networks Considering Bad Relationships

引用

COMPUTER JOURNAL 2015年第6期58卷 1469-1481页

作者： Kim, Sang-Yeon Choi, Dong-Wan Chung, Chin-Wan Korea Adv Inst Sci & Technol Dept Comp Sci Taejon 305701 South Korea

Community detection in social networks is one of the most active problems with lots of applications. Most of the existing works on the problem have focused on detecting the community considering only the closeness between community members. In the real world, however, it is also important to consider bad relationships between members. In this paper, we propose a new variant of the community detection problem, called friendly community search. In the proposed problem, for a given graph, we aim to not only find a densely connected subgraph that contains a given set of query nodes but also minimizes the number of nodes involved in bad relationships in the subgraph. We prove that is Non-deterministic Polynomial-time hard (NP-hard), and develop two novel algorithms, called Greedy and SteinerSwap that return the near optimal solutions. Experimental results show that two proposed algorithms outperform the algorithm adapted from an existing algorithm for the optimal quasi-clique problem.

关键词： community detection social network graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding k Shortest Simple Paths in Directed graphs: A Node Classification algorithm

引用

NETWORKS 2014年第1期64卷 6-17页

作者： Feng, Gang Univ Wisconsin Dept Elect Engn Platteville WI 53818 USA

We propose a new exact algorithm for enumerating k shortest simple paths in a directed graph with n nodes and m edges. The algorithm has a complexity of O(kn(m + n log n)) and follows the same process as Yen's deviation algorithm, but the candidate paths are computed more efficiently using a node classification technique. We first show that a candidate path can be separated by its deviation node as prefix and suffix. Our algorithm then classifies the nodes as red, yellow, and green. A node on the prefix is assigned a red color, a node that can reach t (the destination node) through a shortest path without visiting a red node is assigned a green color, and all other nodes are assigned a yellow color. We prove that when searching for the suffix of a candidate path, all green nodes can be bypassed, and we only need to apply Dijkstra's algorithm to find an all-yellow-node subpath. Since on average the number of yellow nodes is much smaller than n, the new algorithm has a much lower average-case running time. Experiments on many types of networks demonstrate that the new algorithm performs significantly better than existing exact algorithms that have polynomial worst-case complexity. (C) 2014 Wiley Periodicals, Inc.

关键词： graph algorithm k shortest paths node classification simple paths replacement paths Dijkstra's algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient Minimum Spanning Tree algorithms on the Reconfigurable Mesh

引用

Journal of Computer Science & Technology 2000年第2期15卷 116-125页

作者：万颖瑜许胤龙顾晓东陈国良 Department of Computer Science and Technology University of Science and Technology of China National High Performance Computation Center at Hefei Hefei P.R. China

The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, two efficient algorithms are proposed for computing the minimum spanning tree of an n-vertex undirected graph. One runs on an n×n reconfigurable mesh with time complexity of O(log^2 n). The other runs with time complexity of O(log n) on an n^(1+E)×n reconfigurable mesh, where < E < 1 is a constant. All these improve the previously known results on the reconfigurable mesh.

关键词： parallel algorithm reconfigurable mesh graph algorithm minimum spanning tree

来源：评论

学校读者我要写书评

暂无评论

EQUIVALENT APPROXIMATION algorithmS FOR NODE COVER

引用

INFORMATION PROCESSING LETTERS 1986年第6期22卷 291-294页

作者： GUSFIELD, D PITT, L Department of Computer Science Yale University 10 Hillhouse Avenue New Haven CT 06520 U.S.A.

The node cover problem is the problem of determining the minimum size (or weight in the weighted version) node set C in an undirected graph G, so that every edge of G is incident with at least one node of C. Both the weighted and unweighted versions can be estimated to within a factor of 2. There are several intuitive factor-of-2 estimations for the unweighted problem, but the algorithms for the weighted version are somewhat more complex. Here, a linear time factor-of-2 approximation algorithm is presented, based on a familiar heuristic approach; this algorithm is superficially very different from algorithm BE (Bar-Yehuda and Even, 1981) and contains none of its special operations. Although this algorithm is seemingly different from the BE algorithm, these 2 algorithms are shown to be, in a strong sense, equivalent, and the counter-intuitive operations of algorithm BE can be seen as mechanisms to accelerate the running of the presented algorithm.

关键词： Node covering graph algorithm

来源：评论

学校读者我要写书评

暂无评论

On the weighted k-path vertex cover problem

引用

DISCRETE APPLIED MATHEMATICS 2014年 177卷 14-18页

作者： Bresar, B. Krivos-Bellus, R. Semanisin, G. Sparl, P. Pavol Jozef Safarik Univ Kosice Fac Sci Inst Comp Sci Jesenna 5 Kosice 04001 Slovakia Univ Maribor Fac Nat Sci & Math SI-2000 Maribor Slovenia Univ Maribor Fac Org Sci SI-4000 Kranj Slovenia Inst Math Phys & Mech Ljubljana 1000 Slovenia

A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. The cardinality of a minimum k-path vertex cover is called the k-path vertex cover number of a graph G, denoted by psi(k)(G). It is known that the minimum k-path vertex cover problem (k-PVCP) is NP-hard for all k >= 2. In this paper we consider the weighted version of a k-PVCP (k-WPVCP), in which vertices are given weights, and the problem is to find a minimum weight set in G such that the graph obtained by deleting this set from G has no P-k. This problem was briefly introduced by Tu and Zhou (2011) but has not been studied to much extent. We give solutions and efficient algorithms for the k-WPVCP for some special classes of graphs. In particular, for complete graphs and cycles, and most importantly an algorithm that computes the k-path vertex cover number of a tree with time complexity O(*** bar V(G)vertical bar) is presented. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Weighted graph Vertex cover Tree graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Signal-path-level dual-V_t assignment for leakage power

引用

JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS 2006年第2期15卷 197-216页

作者： Wang, Yu Yang, Huazhong Wang, Hui Tsinghua Univ Dept Elect Engn Circuit & Syst Div Beijing 100084 Peoples R China

Along with the fast development of dual-threshold voltage (dual-V-t) and multi-threshold technology, it is possible to use them to reduce static power in low-voltage high-performance circuits. In this paper, we propose a new method to realize CMOS digital circuits that are implemented with dual-V-t technology. We first present a new signal-path-level circuit model which effectively deals with the fact that there can be two threshold voltages assigned to a single gate. In order to assign proper threshold voltage to all the signal-paths in the circuit, our new algorithms introduce the concept of subcircuit extraction and include the hierarchy algorithms which are effective and fast. Experimental results show that our algorithms produce a significant reduction for the ISCAS85 benchmark circuits.

关键词： leakage power dual-threshold voltage static delay model graph algorithm signal-path-level threshold voltage assignment

来源：评论

学校读者我要写书评

暂无评论

algorithms for the Independent Feedback Vertex Set Problem

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2015年第6期E98A卷 1179-1188页

作者： Tamura, Yuma Ito, Takehiro Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan JST ERATO Kawarabayashi Large Graph Project Global Res Ctr Big Data MathNII Tokyo 1018430 Japan

A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the problem of finding an independent feedback vertex set of a given graph with the minimum number of vertices, from the viewpoint of graph classes. This problem is NP-hard even for planar bipartite graphs of maximum degree four. However, we show that the problem is solvable in linear time for graphs having tree-like structures, more specifically, for bounded treewidth graphs, chordal graphs and cographs. We then give a fixed-parameter algorithm for planar graphs when parameterized by the solution size. Such a fixed-parameter algorithm is already known for general graphs, but our algorithm is exponentially faster than the known one.

关键词： fixed parameter tractability graph algorithm independent feedback vertex set

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：