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

Linear-Time algorithms for Maximum-Weight Induced Matchings and Minimum Chain Covers in Convex Bipartite graphs

algorithmICA 2022年第4期84卷 1064-1080页

作者： Klemz, Boris Rote, Guenter Univ Wurzburg Inst Informat D-97074 Wurzburg Germany Free Univ Berlin Inst Informat Takustr 9 D-14195 Berlin Germany

A bipartite graph G = (U, V, E) is convex if the vertices in V can be linearly ordered such that for each vertex u is an element of U, the neighbors of u are consecutive in the ordering of V. An induced matching H of G is amatching for which no edge of E connects endpoints of two different edges of H. We show that in a convex bipartite graph with n vertices and m weighted edges, an induced matching of maximum total weight can be computed in O(n + m) time. An unweighted convex bipartite graph has a representation of size O(n) that records for each vertex u is an element of U the first and last neighbor in the ordering of V. Given such a compact representation, we compute an induced matching of maximum cardinality in O(n) time. In convex bipartite graphs, maximum-cardinality induced matchings are dual to minimum chain covers. A chain cover is a covering of the edge set by chain subgraphs, that is, subgraphs that do not contain induced matchings of more than one edge. Given a compact representation, we compute a representation of a minimum chain cover in O(n) time. If no compact representation is given, the cover can be computed in O(n+ m) time. All of our algorithms achieve optimal linear running time for the respective problem and model, and they improve and generalize the previous results in several ways: The best algorithms for the unweighted problem versions had a running time of O(n(2)) (Brandstadt et al. in Theor. Comput. Sci. 381(1-3):260-265, 2007. https://***/10.1016/***.2007.04.006). The weighted case has not been considered before.

关键词： graph algorithm Induced matching Chain cover Convex bipartite graph Certifying algorithm Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Friedkin-Johnsen Model for Opinion Dynamics on Signed graphs

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2024年第12期36卷 8313-8327页

作者： Zhou, Xiaotian Sun, Haoxin Xu, Wanyue Li, Wei Zhang, Zhongzhi Fudan Univ Sch Comp Sci Shanghai Key Lab Intelligent Informat Proc Shanghai 200433 Peoples R China Fudan Univ Acad Engn & Technol Shanghai 200433 Peoples R China

A signed graph offers richer information than an unsigned graph, since it describes both collaborative and competitive relationships in social networks. In this paper, we study opinion dynamics on a signed graph, based on the Friedkin-Johnsen model. We first interpret the equilibrium opinion in terms of a defined random walk on an augmented signed graph, by representing the equilibrium opinion of every node as a combination of all nodes' internal opinions, with the coefficient of the internal opinion for each node being the difference of two absorbing probabilities. We then quantify some relevant social phenomena and express them in terms of the & ell;(2) norms of vectors. We also design a nearly-linear time signed Laplacian solver for assessing these quantities, by establishing a connection between the absorbing probability of random walks on a signed graph and that on an associated unsigned graph. We further study the opinion optimization problem by changing the initial opinions of a fixed number of nodes, which can be optimally solved in cubic time. We provide a nearly-linear time algorithm with an error guarantee to approximately solve the problem. Finally, we execute extensive experiments on sixteen real-life signed networks, which show that both of our algorithms are effective and efficient, and are scalable to massive graphs with over 20 million nodes.

关键词： Laplace equations Social networking (online) Vectors Approximation algorithms Optimization Mathematical models Heuristic algorithms graph algorithm opinion dynamics opinion optimization polarization signed graph social network

来源：评论

学校读者我要写书评

暂无评论

Metaheuristic algorithms for the bandwidth reduction of large-scale matrices

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第4期43卷 727-784页

作者： Gonzaga de Oliveira, S. L. Carvalho, C. Univ Fed Lavras Dept Ciencia Comp Lavras Brazil

This paper considers the bandwidth reduction problem for large-scale sparse matrices in serial computations. A heuristic for bandwidth reduction reorders the rows and columns of a given sparse matrix. Thus, the method places entries with a nonzero value as close to the main diagonal as possible. Bandwidth optimization is a critical issue for many scientific and engineering applications. This manuscript proposes two heuristics for the bandwidth reduction of large-scale matrices. The first is a variant of the Fast Node Centroid Hill-Climbing algorithm, and the second is an algorithm based on the iterated local search metaheuristic. This paper then experimentally compares the solutions yielded by the new reordering algorithms with the bandwidth solutions delivered by state-of-the-art heuristics for the problem, including tests on large-scale problem matrices. A considerable number of results for a range of realistic test problems showed that the performance of the two new algorithms compared favorably with state-of-the-art heuristics for bandwidth reduction. Specifically, the variant of the Fast Node Centroid Hill-Climbing algorithm yielded the overall best bandwidth results.

关键词： Bandwidth reduction Heuristics Sparse matrices Reordering algorithms Renumbering Ordering Metaheuristics graph algorithm Iterated local search

来源：评论

学校读者我要写书评

暂无评论

CrawlSN: community-aware data acquisition with maximum willingness in online social networks

引用

DATA MINING AND KNOWLEDGE DISCOVERY 2020年第5期34卷 1589-1620页

作者： Hsu, Bay-Yuan Tu, Chia-Lin Chang, Ming-Yi Shen, Chih-Ya Natl Taipei Univ Dept Comp Sci New Taipei Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan

Real social network datasets with community structures are critical for evaluating various algorithms in Online Social Networks (OSNs). However, obtaining such community data from OSNs has recently become increasingly challenging due to privacy issues and government regulations. In this paper, we thus make our first attempt to address two important factors, i.e., user willingness and existence of community structure, to obtain more complete OSN data. We formulate a new research problem, namelyCommunity-aware Data Acquisition with Maximum Willingness in Online Social Networks(CrawlSN), to identify a group of users from an OSN, such that the group is a socially tight community and the users' willingness to contribute data is maximized. We prove that CrawlSN is NP-hard and inapproximable within any factor unless, and propose an effective algorithm, namedCommunity-aware Group Identification with Maximum Willingness(CIW) with various processing strategies. We conduct an evaluation study with 1093 volunteers to validate our problem formulation and demonstrate that CrawlSN outperforms the other alternatives. We also perform extensive experiments on 7 real datasets and show that the proposed CIW outperforms the other baselines in both solution quality and efficiency.

关键词： Social networks graph algorithm Data acquisition

来源：评论

学校读者我要写书评

暂无评论

ON 3-COLORABLE P₅-FREE graphS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2012年第4期26卷 1682-1708页

作者： Maffray, Frederic Morel, Gregory CNRS Lab G SCOP F-38031 Grenoble France UJF Grenoble 1 Lab G SCOP F-38031 Grenoble France

A graph is P-5-free when it does not contain a P-5 (that is, a path with five vertices) as an induced subgraph. The class of P-5-free graphs is of particular interest, especially with respect to the still unknown complexity status of the maximum stable set problem in that class. We investigate the class of 3-colorable P-5-free graphs. We give a complete description of the structure of those graphs and derive a linear-time algorithm that tests membership in this class. Moreover, the algorithm is able to find a maximum weight stable set of a 3-colorable P-5-free graph in linear time.

关键词： graph algorithm structure theorem stability P-5-free graphs

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for Minimizing Edge Crossings in Radial Drawings

引用

algorithmICA 2010年第2期58卷 478-497页

作者： Hong, Seok-Hee Nagamochi, Hiroshi Kyoto Univ Dept Appl Math & Phys Kyoto 606 Japan Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia

We study a crossing minimization problem of drawing a bipartite graph with a radial drawing of two orbits. Radial drawings are one of well-known drawing conventions in social network analysis and visualization, in particular, displaying centrality indices of actors (Wasserman and Faust, Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, 1994). The main problem in this paper is called the one-sided radial crossing minimization, if the positions of vertices in the outer orbit are fixed. The problem is known to be NP-hard (Bachmaier, IEEE Trans. Vis. Comput. graph. 13, 583-594, 2007), and a number of heuristics are available (Bachmaier, IEEE Trans. Vis. Comput. graph. 13, 583-594, 2007). However, there is no approximation algorithm for the crossing minimization problem in radial drawings. We present the first polynomial time constant-factor approximation algorithm for the one-sided radial crossing minimization problem.

关键词： graph drawing Layered drawing Level drawing Hierarchical drawing Radial drawing Crossing minimization Approximation algorithm graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding strongly connected components in distributed graphs

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2005年第8期65卷 901-910页

作者： McLendon, W Hendrickson, B Plimpton, SJ Rauchwerger, L Sandia Natl Labs Dept Computat Sci Albuquerque NM 87185 USA Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

The traditional, serial, algorithm for finding the strongly connected components in a graph is based on depth first search and has complexity which is linear in the size of the graph. Depth first search is difficult to parallelize, which creates a need for a different parallel algorithm for this problem. We describe the implementation of a recently proposed parallel algorithm that finds strongly connected components in distributed graphs, and discuss how it is used in a radiation transport solver. (c) 2005 Elsevier Inc. All rights reserved.

关键词： strongly connected components graph algorithm parallel computing

来源：评论

学校读者我要写书评

暂无评论

On the minimum routing cost clustered tree problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第3期33卷 1106-1121页

作者： Lin, Chen-Wan Wu, Bang Ye Natl Chung Cheng Univ Chiayi 621 Taiwan

For an edge-weighted graph , in which the vertices are partitioned into k clusters , a spanning tree T of G is a clustered spanning tree if T can be cut into k subtrees by removing edges such that each subtree is a spanning tree for one cluster. In this paper, we show the inapproximability of finding a clustered spanning tree with minimum routing cost, where the routing cost is the total distance summed over all pairs of vertices. We present a 2-approximation for the case that the input is a complete weighted graph whose edge weights obey the triangle inequality. We also study a variant in which the objective function is the total distance summed over all pairs of vertices of different clusters. We show that the problem is polynomial-time solvable when the number of clusters k is 2 and NP-hard for . Finally, we propose a polynomial-time 2-approximation algorithm for the case of three clusters.

关键词： Approximation algorithm NP-hard Spanning tree graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Evolving reordering algorithms using an ant colony hyperheuristic approach for accelerating the convergence of the ICCG method

引用

ENGINEERING WITH COMPUTERS 2020年第4期36卷 1857-1873页

作者： de Oliveira, S. L. Gonzaga Silva, L. M. Univ Fed Lavras Dept Ciencia Computacao Lavras Brazil

This paper proposes a novel ant colony hyperheuristic approach for reordering the rows and columns of symmetric positive definite matrices. This ant colony hyperheuristic approach evolves heuristics for bandwidth reduction applied to instances arising from specific application areas with the objective of generating low-cost reordering algorithms. This paper evaluates the resulting reordering algorithm in each application area against state-of-the-art reordering algorithms with the purpose of reducing the running times of the zero-fill incomplete Cholesky-preconditioned conjugate gradient method. The results obtained on a wide-ranging set of standard benchmark matrices show that the proposed approach compares favorably with state-of-the-art reordering algorithms when applied to instances arising from computational fluid dynamics, structural, and thermal problems.

关键词： Bandwidth reduction Profile reduction Heuristics Reordering algorithms Sparse matrices Renumbering Ordering graph labeling Conjugate gradient method graph algorithm Sparse symmetric positive definite linear systems Incomplete Cholesky factorization Ant colony optimization Hyperheuristic

来源：评论

学校读者我要写书评

暂无评论

Approximating the minimum cycle mean

引用

THEORETICAL COMPUTER SCIENCE 2014年第C期547卷 104-116页

作者： Chatterjee, Krishnendu Henzinger, Monika Krinninger, Sebastian Loitzenbauer, Veronika Raskin, Michael A. IST Austria A-3400 Klosterneuburg Austria Univ Vienna Fac Comp Sci A-1090 Vienna Austria Independent Univ Moscow Moscow 115162 Russia Moscow Inst Phys & Technol Dolgoprudnyi 141700 Russia

We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean weight. Our contributions are twofold: (1) First we show that the algorithmic question is reducible to the problem of a logarithmic number of min-plus matrix multiplications of n x n-matrices, where n is the number of vertices of the graph. (2) Second, when the weights are nonnegative, we present the first (1 + is an element of)-approximation algorithm for the problem and the running time of our algorithm is (O) over tilde (n(omega) log(3) (nW/is an element of)/is an element of),(1) where O(n(omega)) is the time required for the classic n x n-matrix multiplication and W is the maximum value of the weights. With an additional O(log(nW/is an element of)) factor in space a cycle with approximately optimal weight can be computed within the same time bound. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Quantitative verification graph algorithm Mean-payoff objective Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：