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

32nd Annual European Symposium on algorithms, ESA 2024

作者： Duraj, Lech Konieczny, Filip Potępa, Krzysztof Faculty of Mathematics and Computer Science Jagiellonian University Kraków Poland

ISBN: (纸本)9783959773386

We develop a framework for algorithms finding the diameter in graphs of bounded distance Vapnik-Chervonenkis dimension, in (parameterized) subquadratic time complexity. The class of bounded distance VC-dimension graphs is wide, including, e.g. all minor-free graphs. We build on the work of Ducoffe et al. [SODA'20, SIGCOMP'22], improving their technique. With our approach the algorithms become simpler and faster, working in O(k · n1−1/d · m · polylog(n)) time complexity for the graph on n vertices and m edges, where k is the diameter and d is the distance VC-dimension of the graph. Furthermore, it allows us to use the improved technique in more general setting. In particular, we use this framework for geometric intersection graphs, i.e. graphs where vertices are identical geometric objects on a plane and the adjacency is defined by intersection. Applying our approach for these graphs, we partially answer a question posed by Bringmann et al. [SoCG'22], finding an O(n7/4 · polylog(n)) parameterized diameter algorithm for unit square intersection graph of size n, as well as a more general algorithm for convex polygon intersection graphs. © Lech Duraj, Filip Konieczny, and Krzysztof Potępa;licensed under Creative Commons License CC-BY 4.0.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Parallel algorithms For Exact SimRank Computations 31

Efficient Parallel Algorithms For Exact SimRank Computations

引用

31st IEEE International Conference on High Performance Computing, Data, and Analytics Workshops, HiPCW 2024

作者： Mundhara, Aditya Nijhara, Prajjwal Banerjee, Dip Sankar Department of Computer Science and Engineering Indian Institute of Technology Jodhpur India

ISBN: (纸本)9798331509118

SimRank is a popular measure for evaluating node similarities in graphs, but its high computational cost limits scalability for large graphs. The ExactSim [1] algorithm achieves precise single-source SimRank similarities but suffers from significant computation time. In this work, we parallelize key components of ExactSim - Personalized PageRank (PPR) computations and SimRank calculations on a CPU-based shared memory multi-core system. By optimizing these modules, we significantly reduce runtime, making ExactSim more practical for large-scale applications. Our results (on graph sizes ranging from 0.1 million edges to 100 million edges) demonstrate the effectiveness of parallelization in improving both efficiency and scalability. © 2024 IEEE

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Combining graphSAGE and Label Propagation for Node Classification in graphs 26th

Combining GraphSAGE and Label Propagation for Node Classif...

引用

26th International Conference on Information Integration and Web Intelligence, iiWAS 2024

作者： Sharma, Dolly Khetarpaul, Sonia Verma, Chinmayi Jain, Prateek Department of Computer Science and Engineering Shiv Nadar Institution of Eminence Deemed to be University Delhi-NCR Uttar Pradesh Greater Noida201314 India

ISBN: (纸本)9783031780899

In node classification tasks, traditional methods like LPA-GCN struggle with scalability and sensitivity to label noise. We propose LPA-graphSAGE, combining the Label Propagation Algorithm with graphSAGE’s sampling and aggregation techniques to address these challenges. Our model outperforms LPA-GCN in accuracy and efficiency, reducing computational costs. Its inductive capabilities also enable effective handling of dynamic graphs with new nodes. Experiments on benchmark datasets confirm that LPA-graphSAGE is a robust and scalable alternative for node classification in complex graphs. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Colorful Vertex Recoloring of Bipartite graphs 42

Colorful Vertex Recoloring of Bipartite Graphs

引用

42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025

作者： Patt-Shamir, Boaz Rosén, Adi Umboh, Seeun William School of Electrical Engineering Tel Aviv University Israel CNRS Université Paris Cité France School of Computing and Information Systems The University of Melbourne Australia Melbourne Australia

ISBN: (纸本)9783959773652

We consider the problem of vertex recoloring: we are given n vertices with their initial coloring, and edges arrive in an online fashion. The algorithm is required to maintain a valid coloring by means of vertex recoloring, where recoloring a vertex incurs a cost. The problem abstracts a scenario of job placement in machines (possibly in the cloud), where vertices represent jobs, colors represent machines, and edges represent "anti affinity" (disengagement) constraints. Online coloring in this setting is a hard problem, and only a few cases were analyzed. One family of instances which is fairly well-understood is bipartite graphs, i.e., instances in which two colors are sufficient to satisfy all constraints. In this case it is known that the competitive ratio of vertex recoloring is Θ(log n). In this paper we propose a generalization of the problem, which allows using additional colors (possibly at a higher cost), to improve overall performance. Concretely, we analyze the simple case of bipartite graphs of bounded largest bond (a bond of a connected graph is an edge-cut that partitions the graph into two connected components). From the upper bound perspective, we propose two algorithms. One algorithm exhibits a trade-off for the uniform-cost case: given Ω(log β) ≤ c ≤ O(log n) colors, the algorithm guarantees that its cost is at most O(logcn ) times the optimal offline cost for two colors, where n is the number of vertices and β is the size of the largest bond of the graph. The other algorithm is designed for the case where the additional colors come at a higher cost, D > 1: given ∆ additional colors, where ∆ is the maximum degree in the graph, the algorithm guarantees a competitive ratio of O(log D). From the lower bounds viewpoint, we show that if the cost of the extra colors is D > 1, no algorithm (even randomized) can achieve a competitive ratio of o(log D). We also show that in the case of general bipartite graphs (i.e., of unbounded bond size), any determinist

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

The Computational Complexity of Factored graphs 16

The Computational Complexity of Factored Graphs

引用

16th Innovations in Theoretical Computer Science Conference, ITCS 2025

作者： Gupta, Shreya Huang, Boyang Impagliazzo, Russell Woo, Stanley Ye, Christopher University of California San Diego La Jolla San DiegoCA United States

ISBN: (纸本)9783959773614

While graphs and abstract data structures can be large and complex, practical instances are often regular or highly structured. If the instance has sufficient structure, we might hope to compress the object into a more succinct representation. An efficient algorithm (with respect to the compressed input size) could then lead to more efficient computations than algorithms taking the explicit, uncompressed object as input. This leads to a natural question: when does knowing the input instance has a more succinct representation make computation easier? We initiate the study of the computational complexity of problems on factored graphs: graphs that are given as a formula of products and unions on smaller graphs. For any graph problem, we define a parameterized version that takes factored graphs as input, parameterized by the number of (smaller) ordinary graphs used to construct the factored graph. In this setting, we characterize the parameterized complexity of several natural graph problems, exhibiting a variety of complexities. We show that a decision version of lexicographically first maximal independent set is XP-complete, and therefore unconditionally not fixed-parameter tractable (FPT). On the other hand, we show that clique counting is FPT. Finally, we show that reachability is XNL-complete. Moreover, XNL is contained in FPT if and only if NL is contained in some fixed polynomial time. © Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, and Christopher Ye.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Small Additive Error for Unsplittable Multicommodity Flow in Outerplanar graphs 22nd

Small Additive Error for Unsplittable Multicommodity Flow i...

引用

22nd International Workshop on Approximation and Online algorithms, WAOA 2024

作者： Shapley, Richard Shmoys, David B. Cornell University Ithaca United States

ISBN: (纸本)9783031813955

We consider an unsplittable version of the minimum max-load multicommodity flow problem, where each demand must be routed along a single path. The objective is to minimize the maximum load on any edge in the network. In a seminal work, Schrijver, Seymour, and Winkler showed how to efficiently solve this problem on a cycle to within an additive term of 32W of the optimal value, where W is the largest demand between any two nodes. We extend their result to outerplanar graphs and provide an efficient algorithm for this problem that exceeds the optimal value by an additive term of no more than O(Wlogk), where k is the number of faces in the graph. This implies an O(logk) approximation ratio. We also extend this result to planar graphs with bounded treewidth and demands on the outer face, for which we also achieve an additive O(Wlogk) error term. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Polynomial Time algorithms for Hop Domination 11th

Polynomial Time Algorithms for Hop Domination

引用

11th International Conference on algorithms and Discrete Applied Mathematics, CALDAM 2025

作者： Karthika, D. Muthucumaraswamy, R. Bhyravarapu, Sriram Kumar, Pritesh Department of Mathematics Sri Venkateswara College of Engineering Kanchipuram Sriperumbudur602117 India The Institute of Mathematical Sciences HBNI Chennai India

ISBN: (纸本)9783031834370

A set S⊆V(G) is said to be a hop dominating set if every vertex u∈V(G)\S, there exists a vertex v∈S such that d(u,v)=2 where d(u, v) represents the distance between u and v in G. The minimum k for which there exists a hop dominating set of size k is called the hop domination number denoted by γh(G). Henning et al. (Inf. Process. Lett. 2020) showed that Hop Domination is NP-hard for bipartite graphs and chordal graphs. The following are the results of this paper. Henning et al. presented a linear time algorithm for solving Hop Domination on bipartite permutation graphs which is a proper subset of biconvex bipartite graphs. In this paper we present a polynomial algorithm for the problem on biconvex bipartite graphs, a superclass of bipartite permutation *** show that Hop Domination is polynomial time solvable on interval graphs which are a subclass of chordal *** initiate the study on this problem from the parameterized complexity perspective. We show that the decision version of Hop Domination is W[1]-hard when parameterized by solution size. Henning et al. presented a linear time algorithm for solving Hop Domination on bipartite permutation graphs which is a proper subset of biconvex bipartite graphs. In this paper we present a polynomial algorithm for the problem on biconvex bipartite graphs, a superclass of bipartite permutation graphs. We show that Hop Domination is polynomial time solvable on interval graphs which are a subclass of chordal graphs. We initiate the study on this problem from the parameterized complexity perspective. We show that the decision version of Hop Domination is W[1]-hard when parameterized by solution size. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Applications of the K-Means and Kosarayu Method for Clustering Switching Devices

Applications of the K-Means and Kosarayu Method for Clusteri...

引用

2025 Systems of Signals Generating and Processing in the Field of on Board Communications, SOSG 2025

作者： Tremasova, L.A. Ustyanseva, E.L. Gadasin, D.V. Gadasin, D.D. Moscow Technical University of Communications and Informatics Moscow Russia

ISBN: (纸本)9798331532635

When transmitting information over a network via communication devices, the parameters of data transmission efficiency and reliability are of paramount importance. Based on the fact that the operator does not have the ability to control traffic along its entire path from the source to the recipient, it is forced to conduct a preliminary assessment, which should take into account not only the number of senders of messages, but also the types of services that customers want to use, which ultimately leads to an increase in the load on the node. To distribute the load between network nodes, you can use their clustering using Kosarayu and k-means algorithms, each of which has its own strengths and weaknesses. The paper considers the possibility of joint application of these methods. © 2025 IEEE.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards a Scalable Parallel Infomap Algorithm for Community Detection 32

Towards a Scalable Parallel Infomap Algorithm for Community ...

引用

32nd Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)

作者： Santos, Gabriel G. Lakhotia, Kartik De Rose, Cesar A. F. Pontificia Univ Catolica Rio Grande do Sul Sch Technol Porto Alegre Brazil Intel Labs Santa Clara CA USA

ISBN: (纸本)9798350363074;9798350363081

Identifying Community structures is a fundamental problem in graph analysis. To detect communities in massive contemporary graphs, researchers have extensively explored shared- and distributed-memory parallel algorithms for several methods including Louvain Modularity Optimization and Label Propagation. The widely used Infomap algorithm based on Map Equation Framework (MEF) is known to provide better quality results than other approaches. However, research on parallel community detection using MEF or Infomap is extremely sparse when compared to other methods. We present a comprehensive characterization of Infomap and some of its known parallel implementations to facilitate research into parallel algorithms based on MEF. Most implementations take simple parallelization approaches, leaving strategies used to parallelize similar algorithms such as Louvain untouched. We highlight the scalability limitations of current implementations and implement and evaluate optimizations for MEF based parallel community detection that achieved up to 119% improvement on the overall speedup across the tested datasets.

关键词： community detection graph algorithms parallel computing

来源：评论

学校读者我要写书评

暂无评论

The power of adaptivity in source identification with time queries on the path

引用

THEORETICAL COMPUTER SCIENCE 2022年 911卷 92-123页

作者： Lecomte, Victor Odor, Gergely Thiran, Patrick Stanford Univ Stanford CA 94305 USA EPFL Zurich Switzerland

We study the problem of identifying the source of a stochastic diffusion process spreading on a graph based on the arrival times of the diffusion at a few queried nodes. In a graph G = (V, E), an unknown source node v* is an element of V is drawn uniformly at random, and unknown edge weights w(e) for e is an element of E, representing the propagation delays along the edges, are drawn independently from a Gaussian distribution of mean 1 and variance sigma(2). An algorithm then attempts to identify v* by querying nodes q is an element of V and being told the length of the shortest path between q and v* in graph G weighted by w. We consider two settings: non-adaptive, in which all query nodes must be decided in advance, and adaptive, in which each query can depend on the results of the previous ones. Both settings are motivated by an application of the problem to epidemic processes (where the source is called patient zero), which we discuss in detail. We characterize the query complexity when G is an n-node path. In the non-adaptive setting, Theta(n alpha(2)) queries are needed for sigma(2) <= 1, and Theta(n) for sigma(2) >= 1. In the adaptive setting, somewhat surprisingly, only Theta(log log(1/sigma) n) are needed when sigma(2) <= 1/2, and O(log log n) + O-sigma(1) when sigma(2) >= 1/2. This is the first mathematical study of source identification with time queries in a non-deterministic diffusion process. (c) 2022 The Author(s). Published by Elsevier B.V.

关键词： graph algorithms Source location Noisy information Lower bounds

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：