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

24th International Conference on Neural Information Processing (ICONIP)

作者： Wu, Hongchun Shang, Jiaxing Zhou, Shangbo Feng, Yong Chongiqng Univ Coll Comp Sci Chongqing Peoples R China Chongqing Univ Key Lab Dependable Serv Comp Cyber Phys Soc Minist Educ Chongqing Peoples R China

ISBN: (纸本)9783319701394;9783319701387

Influence maximization is the problem of finding k seed nodes in a given network as information sources so that the influence cascade can be maximized. To solve this problem both efficiently and effectively, in this paper we propose LAIM: a linear time algorithm for influence maximization in large-scale social networks. Our LAIM algorithm consists of two parts: (1) influence computation;and (2) seed nodes selection. The first part approximates the influence of any node using its local influence, which can be efficiently computed with an iterative algorithm. The second part selects seed nodes in a greedy manner based on the results of the first part. We theoretically prove that the time and space complexities of our algorithm are proportional to the network size. Experimental results on six real-world datasets show that our approach significantly outperforms other state-of-the-art algorithms in terms of influence spread, running time and memory usage.

关键词： Influence maximization Social networks linear time algorithm Computational complexity Data mining

来源：评论

学校读者我要写书评

暂无评论

A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width

A simpler linear time algorithm for embedding graphs into an...

引用

49th Annual Symposium on Foundations-of-Computer-Science

作者： Kawarabayashi, Ken-ichi Mohar, Bojan Reed, Bruce Natl Inst Informat Chiyoda Ku 2-1-2 Hitotsubashi Tokyo 1018430 Japan Simon Fraser Univ G Theory CRC Dept Math Burnaby BC Canada McGill Univ G Theory CRC Montreal PQ Canada

ISBN: (纸本)9780769534367

For every fixed surface S, orientable or non-orientable, and a given graph G, Mohar (STOC'96 and Siam J. Discrete Math. (1999)) described a linear time algorithm which yields either an embedding of G in S or a minor of G which is not embeddable in S and is minimal with this property. That algorithm, however, needs a lot of lemmas which spanned six additional papers. In this paper, we give a new linear time algorithm for the same problem. The advantages of our algorithm are the following: 1. The proof is considerably simpler: it needs only about 10 pages, and some results (with rather accessible proofs)from graph minors theory, while Mohar's original algorithm and its proof occupy more than 100 pages in total. 2. The hidden constant (depending on the genus g of the surface S) is much smaller It is singly exponential in g, while it is doubly exponential in Mohar's algorithm. As a spinoff of our main result, we give another linear time algorithm, which is of independent interest. This algorithm computes the genus and constructs minimum genus embed dings of graphs of bounded tree-width. This resolves a conjecture by Neil Robertson and solves one of the most annoying long standing open question about complexity of algorithms on graphs of bounded tree-width.

关键词： linear time algorithm Embedding Surface Genus of a graph Tree-width

来源：评论

学校读者我要写书评

暂无评论

A linear time algorithm for Ordered Partition 9th

A Linear Time Algorithm for Ordered Partition

引用

9th International Frontiers of algorithmics Workshop (FAW)

作者： Han, Yijie Univ Missouri Sch Comp & Engn Kansas City MO 64110 USA

We present a deterministic linear time and space algorithm for ordered partition of a set T of n integers into n(1/2) sets T-0 <= T-1 <= ... T-n1/2 (-) (1), where vertical bar T-i vertical bar = theta(n(1/2)) an... 详细信息

ISBN: (纸本)9783319196473;9783319196466

关键词： algorithms Sorting Integer sorting linear time algorithm Ordered partition Hashing Perfect hash functions

来源：评论

学校读者我要写书评

暂无评论

A linear time algorithm for the Line Subgraph Problem in Halin Graphs

A Linear Time Algorithm for the Line Subgraph Problem in Hal...

引用

2016 International Conference on Applied Mathematics, Simulation and Modelling(AMSM2016)

作者： Dingjun Lou Jun Liang Guanpu Han School of Data and Computer Science Sun Yat-sen University

Given a graph G=(V,E) and a positive integer p≤|E|. The Line Subgraph Problem is: Is there a subset E'?E such that |E'|≥p and H=(V,E) is a line graph. In this paper, we design a linear time algorithm to solv... 详细信息

ISBN: (纸本)9781510833890

关键词： halin graph line graph linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Simple linear time approximation algorithm for betweenness

引用

OPERATIONS RESEARCH LETTERS 2012年第6期40卷 450-452页

作者： Makarychev, Yury Toyota Technol Inst Chicago IL 60637 USA

We study the Betweenness problem. We are given a set of vertices and betweenness constraints. Each betweenness constraint of the form x similar to {y, z} requires that vertex x lies between vertices y and z. Our goal is to find a vertex ordering that maximizes the number of satisfied constraints. In 1995, Chor and Sudan designed an SDP algorithm that satisfies half of all constraints in a satisfiable instance. We present a simple combinatorial linear time algorithm with the same approximation guarantee. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Betweenness problem Approximation algorithm linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for clique-coloring problem in circular-arc graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第1期33卷 147-155页

作者： Liang, Zuosong Shan, Erfang Zhang, Yuzhong Qufu Normal Univ Sch Management Rizhao 276800 Peoples R China Shanghai Univ Sch Management Shanghai 200444 Peoples R China Shanghai Univ Dept Math Shanghai 200444 Peoples R China

A maximal clique of G is a clique not properly contained in any other clique. A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that no maximal clique with at least two vertices is monochromatic. The smallest integer k admitting a k-clique-coloring of G is called clique-coloring number of G. Cerioli and Korenchendler (Electron Notes Discret Math 35:287-292, 2009) showed that there is a polynomial-time algorithm to solve the clique-coloring problem in circular-arc graphs and asked whether there exists a linear-time algorithm to find an optimal clique-coloring in circular-arc graphs or not. In this paper we present a linear-time algorithm of the optimal clique-coloring in circular-arc graphs.

关键词： Clique-coloring Circular-arc graph linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

linear-time algorithm for Quantum 2SAT

引用

THEORY OF COMPUTING 2018年第1期14卷 1-27页

作者： Arad, Itai Santha, Miklos Sundaram, Aarthi Zhang, Shengyu Technion Israel Inst Technol Haifa Israel Univ Paris Diderot Rech Paris France Univ Maryland Joint Ctr Quantum Informat & Comp Sci College Pk MD 20742 USA Chinese Univ Hong Kong Hong Kong Hong Kong Peoples R China

A well-known result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the N P-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors pi(ij) on a system of n qubits, and the task is to decide whether the Hamiltonian H = Sigma pi(ij) has a 0-eigenvalue, or all eigenvalues are greater than 1/n(alpha) for some alpha = O(1). The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding a ground state of 2-local frustration-free Hamiltonians of spin 1/2, a well-studied model believed to capture certain key properties in modern condensed matter physics. Bravyi has shown that the quantum 2-SAT problem has a deterministic algorithm of complexity O(n(4)) in the algebraic model of computation where every arithmetic operation on complex numbers can be performed in unit time, and n is the number of variables. In this paper we give a deterministic algorithm in the algebraic model with running time O(n + m), where m is the number of local projectors, therefore achieving the best possible complexity in that model. We also show that if in the input every number has a constant size representation then the bit complexity of our algorithm is O((n+m)M(n)), where M(n) denotes the complexity of multiplying two n-bit integers.

关键词： quantum satisfiability davis-putnam procedure linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Medians in median graphs and their cube complexes in linear time

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 126卷 80-105页

作者： Beneteau, Laurine Chalopin, Jeremie Chepoi, Victor Vaxes, Yann Aix Marseille Univ Lab Informat & Syst Marseille France CNRS Paris France

The median of a set of vertices P of a graph G is the set of all vertices x of G minimizing the sum of distances from x to all vertices of P. In this paper, we present a linear time algorithm to compute medians in median graphs. We also present a linear time algorithm to compute medians in the associated L-1-cube complexes. Our algorithm is based on the majority rule characterization of medians in median graphs and on a fast computation of parallelism classes of edges (0-classes) via Lexicographic Breadth First Search (LexBFS). We show that any LexBFS ordering of the vertices of a median graph satisfies the following fellow traveler property: the parents of any two adjacent vertices are also adjacent. Using the fast computation of the 0-classes, we also compute the Wiener index (total distance) in linear time and the distance matrix in optimal quadratic time. (C)& nbsp;2022 Elsevier Inc. All rights reserved.

关键词： Median graph CAT(0) cube complex Event structures Median problem linear time algorithm LexBFS

来源：评论

学校读者我要写书评

暂无评论

Maximum Induced Matchings for Chordal Graphs in linear time

引用

algorithmICA 2008年第4期52卷 440-447页

作者： Brandstadt, Andreas Hoang, Chinh T. Wilfrid Laurier Univ Dept Phys & Comp Sci Waterloo ON N2L 3C5 Canada Univ Rostock Inst Informat D-18051 Rostock Germany

The Maximum Induced Matching ( MIM) Problem asks for a largest set of pairwise vertex- disjoint edges in a graph which are pairwise of distance at least two. It is well- known that the MIM problem is NP- complete even on particular bipartite graphs and on line graphs. On the other hand, it is solvable in polynomial time for various classes of graphs ( such as chordal, weakly chordal, interval, circular- arc graphs and others) since the MIM problem on graph G corresponds to the Maximum Independent Set problem on the square G* = L( G) 2 of the line graph L( G) of G, and in some cases, G* is in the same graph class;for example, for chordal graphs G, G* is chordal. The construction of G*, however, requires O( m2) time, where m is the number of edges in G. Is has been an open problem whether there is a linear- time algorithm for the MIM problem on chordal graphs. We give such an algorithm which is based on perfect elimination order and LexBFS.

关键词： Maximum induced matchings Chordal graphs Perfect elimination order Lexicographic breadth-first search linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

linear time-approximation algorithms for bin packing

引用

OPERATIONS RESEARCH LETTERS 2000年第5期26卷 217-222页

作者： Zhang, GC Cai, XQ Wong, CK Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China

Simchi-Levi (Naval Res. Logist. 41 (1994) 579-585) proved that the famous bin packing algorithms FF and BF have an absolute worst-case ratio of no more than 7/4, and FFD and BFD have an absolute worst-case ratio of 3/2, respectively. These algorithms run in time O(n log n). In this paper, we provide a linear time constant space (number of bins kept during the execution of the algorithm is constant) off-line approximation algorithms with absolute worst-case ratio 3/2. This result is best possible unless P = NP. Furthermore, we present a linear time constant space on-line algorithm and prove that the absolute worst-case ratio is 7/4. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： bin packing absolute worst-case ratio linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：