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

2024 IEEE International Conference on Big Data, BigData 2024

作者： Kiran, Mekala Das, Apurba Banerjee, Suman Birla Institute of Technology & Science Hyderabad India Indian Institute of Technology Jammu Jammu & Kashmir India

ISBN: (纸本)9798350362480

Analysis of large-scale networks for different structural patterns (also called motifs) remains an active area of research in the domain of graph data management and mining. In the past three decades, research has led to a large volume of literature in this area. However, the literature in the context of a signed bipartite graph is limited. In this paper, we study the problem of counting the balanced motifs in a signed bipartite graph. Specifically, We design an efficient algorithm BB2K for counting balanced (2, k)-bicliques. Previous studies for balanced bicliques in a signed bipartite graph focus on a set enumeration-based approach. We observe that the set enumeration-based approaches are expensive as they need to discard a large number of structures, which are not balanced. We take a different approach where we systematically group the symmetric and asymmetric wedges and count the balanced bicliques by counting on those wedges in such a way that we eliminate the generation of unbalanced structures completely. We conducted experiments with nine real-life datasets, and the experimental results demonstrate that our algorithm BB2K is more than 100× faster than the baseline SBCList++ - an adaptation of the state-of-the-art algorithm BCList++ combined with the filtering technique to filter out unbalanced bicliques. We have also shown the scalability of the proposed algorithm by using datasets of different sizes in our experiments. © 2024 IEEE.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Make Flows Small Again: Revisiting the Flow Framework 29th

Make Flows Small Again: Revisiting the Flow Framework

引用

29th International Conference on Tools and algorithms for the Construction and Analysis of Systems (TACAS)

作者： Meyer, Roland Wies, Thomas Wolff, Sebastian TU Braunschweig Braunschweig Germany NYU New York NY 10012 USA

ISBN: (纸本)9783031308222;9783031308239

We present a new flow framework for separation logic reasoning about programs that manipulate general graphs. The framework overcomes problems in earlier developments: it is based on standard fixed point theory, guarantees least flows, rules out vanishing flows, and has an easy to understand notion of footprint as needed for soundness of the frame rule. In addition, we present algorithms for automating the frame rule, which we evaluate on graph updates extracted from linearizability proofs for concurrent data structures. The evaluation demonstrates that our algorithms help to automate key aspects of these proofs that have previously relied on user guidance or heuristics.

关键词： Separation Logic graph algorithms Frame Inference

来源：评论

学校读者我要写书评

暂无评论

Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch 2023

Deterministic Incremental APSP with Polylogarithmic Update T...

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Forster, Sebastian Nazari, Yasamin Gutenberg, Maximilian Probst Salzburg Univ Salzburg Austria Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450399135

We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylogarithmic amortized update time and answers queries for the distance between any pair of vertices in the current graph with a polylogarithmic approximation in O(log log n) time. Prior to this work, no data structure was known for partially dynamic graphs, i.e., graphs undergoing either edge insertions or deletions, with less than n(o(1)) update time except for dense graphs, even when allowing randomization against oblivious adversaries or considering only single-source distances.

关键词： Dynamic algorithms Shortest paths graph algorithms

来源：评论

学校读者我要写书评

暂无评论

ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems 1

引用

20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR)

作者： Ito, Takehiro Kawahara, Jun Nakahata, Yu Soh, Takehide Suzuki, Akira Teruyama, Junichi Toda, Takahisa Tohoku Univ Grad Sch Informat Sci Sendai Japan Kyoto Univ Grad Sch Informat Kyoto Japan Nara Inst Sci & Technol Grad Sch Sci & Technol Ikoma Japan Kobe Univ Informat Infrastruct & Digital Transformat Initia Kobe Japan Univ Hyogo Grad Sch Informat Sci Kobe Japan Univ Electrocommun Grad Sch Informat & Engn Chofu Japan

ISBN: (数字)9783031332715

ISBN: (纸本)9783031332708;9783031332715

This paper proposes an algorithmic framework for solving various combinatorial reconfiguration problems by using zero-suppressed binary decision diagrams (ZDDs), a data structure for representing families of sets. In general, a reconfiguration problem checks if there is a step-by-step transformation between two given feasible solutions (e.g., independent sets of an input graph) of a fixed search problem, such that all intermediate results are also feasible and each step obeys a fixed reconfiguration rule (e.g., adding/removing a single vertex to/from an independent set). The solution space formed by all feasible solutions can be exponential in the input size, and indeed, many reconfiguration problems are known to be PSPACE-complete. This paper shows that an algorithm in the proposed framework efficiently conducts breadth-first search by compressing the solution space using ZDDs, and that it finds a shortest transformation between two given feasible solutions if such a transformation exists. Moreover, the proposed framework provides rich information on the solution space, such as its connectivity and all feasible solutions that are reachable from a specified one. Finally, we demonstrate that the proposed framework can be applied to various reconfiguration problems, and experimentally evaluate its performance.

关键词： Combinatorial reconfiguration graph algorithms Binary decision diagrams

来源：评论

学校读者我要写书评

暂无评论

Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! 64

Negative-Weight Single-Source Shortest Paths in Near-Linear ...

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Bringmann, Karl Cassis, Alejandro Fischer, Nick Saarland Univ Saarbrucken Germany Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany Weizmann Inst Sci Rehovot Israel

ISBN: (纸本)9798350318944

In this work we revisit the fundamental Single-Source Shortest Paths (SSSP) problem with possibly negative edge weights. A recent breakthrough result by Bernstein, Nanongkai and Wulff-Nilsen established a near-linear O(m log(8) (n) log(W))-time algorithm for negative-weight SSSP, where W is an upper bound on the magnitude of the smallest negative-weight edge. In this work we improve the running time to O(m log(2) (n) log(nW) log log n), which is an improvement by nearly six log-factors. Some of these log-factors are easy to shave (e.g. replacing the priority queue used in Dijkstra's algorithm), while others are significantly more involved (e.g. to find negative cycles we design an algorithm reminiscent of noisy binary search and analyze it with drift analysis). As side results, we obtain an algorithm to compute the minimum cycle mean in the same running time as well as a new construction for computing Low-Diameter Decompositions in directed graphs.

关键词： graph algorithms shortest paths algorithms

来源：评论

学校读者我要写书评

暂无评论

Engineering Massively Parallel MST algorithms 37

Engineering Massively Parallel MST Algorithms

引用

37th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Sanders, Peter Schimek, Matthias Karlsruhe Inst Technol Inst Theoret Informat Karlsruhe Germany

ISBN: (纸本)9798350337662

We develop and extensively evaluate highly scalable distributed-memory algorithms for computing minimum spanning trees (MSTs). At the heart of our solutions is a scalable variant of Bor degrees uvka's algorithm. For partitioned graphs with many local edges we improve this with an effective form of contracting local parts of the graph during a preprocessing step. We also adapt the filtering concept of the best practical sequential algorithm to develop a massively parallel Filter-Bor degrees uvka algorithm that is very useful for graphs with poor locality and high average degree. Our experiments indicate that our algorithms scale well up to at least 65 536 cores and are up to 800 times faster than previous distributed MST algorithms.

关键词： graph algorithms distributed algorithms minimum spanning tree MPI

来源：评论

学校读者我要写书评

暂无评论

Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n Barrier 64

Folklore Sampling is Optimal for Exact Hopsets: Confirming t...

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Bodwin, Greg Hoppenworth, Gary Univ Michigan Comp Sci & Engn Ann Arbor MI 48109 USA

ISBN: (纸本)9798350318944

For a graph G, a D-diameter-reducing exact hopset is a small set of additional edges H that, when added to G, maintains its graph metric but guarantees that all node pairs have a shortest path in G boolean OR H using at most D edges. A shortcut set is the analogous concept for reachability rather than distances. These objects have been studied since the early '90s, due to applications in parallel, distributed, dynamic, and streaming graph algorithms. For most of their history, the state-of-the-art construction for either object was a simple folklore algorithm, based on randomly sampling nodes to hit long paths in the graph. However, recent breakthroughs of Kogan and Parter [SODA '22] and Bernstein and Wein [SODA '23] have finally improved over the folklore algorithm for shortcut sets and for (1 + epsilon)-approximate hopsets. For either object, it is now known that one can use O(n) hop-edges to reduce diameter to (O) over tilde (n(1/3)), improving over the folklore diameter bound of (O) over tilde (n(1/2)). The only setting in which folklore sampling remains unimproved is for exact hopsets. Can these improvements be continued? We settle this question negatively by constructing graphs on which any exact hopset of O(n) edges has diameter (Omega) over tilde (n(1/2)). This improves on the previous lower bound of Omega(n(1/3)) by Kogan and Parter [FOCS '22]. Using similar ideas, we also polynomially improve the current lower bounds for shortcut sets, constructing graphs on which any shortcut set of O(n) edges reduces diameter to e (Omega) over tilde (n(1/4)). This improves on the previous lower bound of (Omega) over tilde (n(1/6)) by Huang and Pettie [SIAM J. Disc. Math. '18]. We also extend our constructions to provide lower bounds against O(p)-size exact hopsets and shortcut sets for other values of p;in particular, we show that folklore sampling is near-optimal for exact hopsets in the entire range of parameters p is an element of [1, n(2)].

关键词： graph theory graph data structures graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Deterministic Massively Parallel Symmetry Breaking for Sparse graphs 23

Deterministic Massively Parallel Symmetry Breaking for Spars...

引用

35th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Fischer, Manuela Giliberti, Jeff Grunau, Christoph Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450395458

We consider the problem of designing deterministic graph algorithms for the model of Massively Parallel Computation (MPC) that improve with the sparsity of the input graph, as measured by the standard notion of arboricity. For the problems of maximal independent set (MIS), maximal matching (MM), and vertex coloring, we improve the state of the art as follows. Let lambda denote the arboricity of the..-node input graph with maximum degree Delta. MIS andMM. We develop a low-space MPC algorithm that deterministically reduces the maximum degree to poly(lambda) in O(log log n) rounds, improving and simplifying the randomized O(log log n)-round poly(max(lambda, log n))-degree reduction of Ghaffari, Grunau, Jin [DISC'20]. Our approach when combined with the state-of-the-art O(log Delta + log log n)-round algorithm by Czumaj, Davies, Parter [SPAA'20, TALG'21] leads to an improved deterministic round complexity of O(log lambda + log log n). The above MIS and MM algorithm however works in the setting where the global memory allowed, i.e., the number of machines times the local memory per machine, is superlinear in the input size. We extend them to obtain the first low-space MIS and MM algorithms that work with linear global memory. Specifically, we show that both problems can be solved in deterministic time O(log lambda center dot log log(lambda) n), and even in O(log log n) time for graphs with arboricity at most log(O(1)) log n. In this setting, only a O(log(2) log n)-running time bound for trees was known due to Latypov and Uitto [ArXiv'21]. Vertex Coloring. We present a O(1)-round deterministic algorithm for the problem of O(lambda)-coloring in the linear-memory regime of MPC, with relaxed global memory of n center dot poly(lambda). This matches the round complexity of the state-of-the-art randomized algorithm by Ghaffari and Sayyadi [ICALP'19] and significantly improves upon the deterministic O(lambda(epsilon))-round algorithm by Barenboim and Khazanov [CSR'18]. Our algor

关键词： deterministic algorithms distributed computing massively parallel computation sparse graphs graph algorithms derandomization

来源：评论

学校读者我要写书评

暂无评论

Provably-Efficient and Internally-Deterministic Parallel Union-Find 23

Provably-Efficient and Internally-Deterministic Parallel Uni...

引用

35th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Fedorov, Alexander Hashemi, Diba Nadiradze, Giorgi Alistarh, Dan IST Austria Klosterneuburg Austria

ISBN: (纸本)9781450395458

Determining the degree of inherent parallelism in classical sequential algorithms and leveraging it for fast parallel execution is a key topic in parallel computing, and detailed analyses are known for a wide range of classical algorithms. In this paper, we perform the first such analysis for the fundamental Union-Find problem, in which we are given a graph as a sequence of edges, and must maintain its connectivity structure under edge additions. We prove that classic sequential algorithms for this problem are well-parallelizable under reasonable assumptions, addressing a conjecture by [Blelloch, 2017]. More precisely, we show via a new potential argument that, under uniform random edge ordering, parallel union-find operations are unlikely to interfere: T concurrent threads processing the graph in parallel will encounter memory contention O(T-2 center dot log vertical bar V vertical bar center dot log vertical bar E vertical bar) times in expectation, where vertical bar E vertical bar and vertical bar V vertical bar are the number of edges and nodes in the graph, respectively. We leverage this result to design a new parallel Union-Find algorithm that is both internally deterministic, i.e., its results are guaranteed to match those of a sequential execution, but also work-efficient and scalable, as long as the number of threads T is O(vertical bar E vertical bar(1/3-epsilon)), for an arbitrarily small constant epsilon > 0, which holds for most large real-world graphs. We present lower bounds which show that our analysis is close to optimal, and experimental results suggesting that the performance cost of internal determinism is limited.

关键词： union-find parallel algorithms graph algorithms deterministic parallelism

来源：评论

学校读者我要写书评

暂无评论

Decremental optimization of vertex-colouring under the reconfiguration framework

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS- COMPUTER SYSTEMS THEORY 2023年第1期8卷 80-92页

作者： Yanagisawa, Yusuke Suzuki, Akira Tamura, Yuma Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Japan

Suppose that we are given a positive integer k, and a k-(vertex-)colouring f 0 of a given graph G. Then we are asked to find a colouring of G using the minimum number of colours among colourings that are reachable from f 0 by iteratively changing a colour assignment of exactly one vertex while maintaining the property of k-colourings. In this paper, we give linear-time algorithms to solve the problem for graphs of degeneracy at most two and for the case where k = 3 . These results imply linear-time algorithms for series-parallel graphs and grid graphs. In addition, we give linear-time algorithms for chordal graphs and cographs. On the other hand, we show that, for any k = 4 , this problem remains NP-hard for planar graphs with degeneracy three and maximum degree four. Thus, we obtain a complexity dichotomy for this problem with respect to the degeneracy of a graph and the number k of colours.

关键词： Combinatorial reconfiguration graph algorithms graph colouring linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：