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

32nd Annual European Symposium on algorithms, ESA 2024

作者： Katz, Matthew J. Saban, Rachel Sharir, Micha Department of Computer Science Ben-Gurion University of the Negev Beer Sheva Israel School of Computer Science Tel Aviv University Israel

ISBN: (纸本)9783959773386

We present several near-linear algorithms for problems involving visibility over a 1.5-dimensional terrain. Concretely, we have a 1.5-dimensional terrain T, i.e., a bounded x-monotone polygonal path in the plane, with n vertices, and a set P of m points that lie on or above T. The visibility graph V G(P, T) is the graph with P as its vertex set and {(p, q) | p and q are visible to each other} as its edge set. We present algorithms that perform BFS and DFS on V G(P, T), which run in O(n log n + m log3(m + n)) time. We also consider three optimization problems, in which P is a set of points on T, and we erect a vertical tower of height h at each p ∈ P. In the first problem, called the reverse shortest path problem, we are given two points s, t ∈ P, and an integer k, and wish to find the smallest height h∗ for which V G(P(h∗), T) contains a path from s to t of at most k edges, where P(h∗) is the set of the tips of the towers of height h∗ erected at the points of P. In the second problem we wish to find the smallest height h∗ for which V G(P(h∗), T) contains a cycle, and in the third problem we wish to find the smallest height h∗ for which V G(P(h∗), T) is nonempty;we refer to that problem as "Seeing the most without being seen". We present algorithms for the first two problems that run in O∗((m + n)6/5) time, where the O∗(·) notation hides subpolynomial factors. The third problem can be solved by a faster algorithm, which runs in O((n + m) log3(m + n)) time. © Matthew J. Katz, Rachel Saban, and Micha Sharir;licensed under Creative Commons License CC-BY 4.0.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

How to Reduce Temporal Cliques to Find Sparse Spanners 32

How to Reduce Temporal Cliques to Find Sparse Spanners

引用

32nd Annual European Symposium on algorithms, ESA 2024

作者： Angrick, Sebastian Bals, Ben Friedrich, Tobias Gawendowicz, Hans Hastrich, Niko Klodt, Nicolas Lenzner, Pascal Schmidt, Jonas Skretas, George Wells, Armin Faculty of Digital Engineering Hasso Plattner Institute University of Potsdam Germany

ISBN: (纸本)9783959773386

Many real-world networks, such as transportation or trade networks, are dynamic in the sense that the edge-set may change over time, but these changes are known in advance. This behavior is captured by the temporal graphs model, which has recently become a trending topic in theoretical computer science. A core open problem in the field is to prove the existence of linear-size temporal spanners in temporal cliques, i.e., sparse subgraphs of complete temporal graphs that ensure all-pairs reachability via temporal paths. So far, the best known result is the existence of temporal spanners with O(n log n) many edges. We present significant progress towards proving whether linear-size temporal spanners exist in all temporal cliques. We adapt techniques used in previous works and heavily expand and generalize them. This allows us to show that the existence of a linear spanner in cliques and bi-cliques is equivalent and using this, we provide a simpler and more intuitive proof of the O(n log n) bound by giving an efficient algorithm for finding linearithmic spanners. Moreover, we use our novel and efficiently computable approach to show that a large class of temporal cliques, called edge-pivotable graphs, admit linear-size temporal spanners. To contrast this, we investigate other classes of temporal cliques that do not belong to the class of edge-pivotable graphs. We introduce two such graph classes and we develop novel algorithmic techniques for establishing the existence of linear temporal spanners in these graph classes as well. © Sebastian Angrick, Ben Bals, Tobias Friedrich, Hans Gawendowicz, Niko Hastrich, Nicolas Klodt, Pascal Lenzner, Jonas Schmidt, George Skretas, and Armin Wells;licensed under Creative Commons License CC-BY 4.0.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Worst-Case to Expander-Case Reductions: Derandomized and Generalized 32

Worst-Case to Expander-Case Reductions: Derandomized and Gen...

引用

32nd Annual European Symposium on algorithms, ESA 2024

作者： Abboud, Amir Wallheimer, Nathan Weizmann Institute of Science Rehovot Israel

ISBN: (纸本)9783959773386

A recent paper by Abboud and Wallheimer [ITCS 2023] presents self-reductions for various fundamental graph problems, which transform worst-case instances to expanders, thus proving that the complexity remains unchanged if the input is assumed to be an expander. An interesting corollary of their self-reductions is that if some problem admits such reduction, then the popular algorithmic paradigm based on expander-decompositions is useless against it. In this paper, we improve their core gadget, which augments a graph to make it an expander while retaining its important structure. Our new core construction has the benefit of being simple to analyze and generalize while obtaining the following results: A derandomization of the self-reductions, showing that the equivalence between worst-case and expander-case holds even for deterministic algorithms, and ruling out the use of expander-decompositions as a derandomization tool. An extension of the results to other models of computation, such as the Fully Dynamic model and the Congested Clique model. In the former, we either improve or provide an alternative approach to some recent hardness results for dynamic expander graphs by Henzinger, Paz, and Sricharan [ESA 2022]. In addition, we continue this line of research by designing new self-reductions for more problems, such as Max-Cut and dynamic Densest Subgraph, and demonstrating that the core gadget can be utilized to lift lower bounds based on the OMv Conjecture to expanders. © Amir Abboud and Nathan Wallheimer;licensed under Creative Commons License CC-BY 4.0.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Breaking the Barrier 2k for Subset Feedback Vertex Set in Chordal graphs 49

Breaking the Barrier 2k for Subset Feedback Vertex Set in Ch...

引用

49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024

作者： Bai, Tian Xiao, Mingyu School of Computer Science and Engineering University of Electronic Science and Technology of China Chengdu China

ISBN: (纸本)9783959773355

The Subset Feedback Vertex Set problem (SFVS) is to delete k vertices from a given graph such that in the remaining graph, any vertex in a subset T of vertices (called a terminal set) is not in a cycle. The famous Feedback Vertex Set problem is the special case of SFVS with T being the whole set of vertices. In this paper, we study exact algorithms for SFVS in Split graphs (SFVS-S) and SFVS in Chordal graphs (SFVS-C). SFVS-S generalizes the minimum vertex cover problem and the prize-collecting version of the maximum independent set problem in hypergraphs (PCMIS), and SFVS-C further generalizes SFVS-S. Both SFVS-S and SFVS-C are implicit 3-Hitting Set problems. However, it is not easy to solve them faster than 3-Hitting Set. In 2019, Philip, Rajan, Saurabh, and Tale (Algorithmica 2019) proved that SFVS-C can be solved in O*p2kq time, slightly improving the best result O*p2.0755kq for 3-Hitting Set. In this paper, we break the "2k-barrier" for SFVS-S and SFVS-C by introducing an O*p1.8192kq-time algorithm. This achievement also indicates that PCMIS can be solved in O*p1.8192nq time, marking the first exact algorithm for PCMIS that outperforms the trivial O*p2nq threshold. Our algorithm uses reduction and branching rules based on the Dulmage-Mendelsohn decomposition and a divide-and-conquer method. © Tian Bai and Mingyu Xiao.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

LLM Performance Assessment in Computer Science Graduate Entrance Exams 11

LLM Performance Assessment in Computer Science Graduate Entr...

引用

11th International Symposium on Telecommunication, IST 2024

作者： Varastehnezhad, Arya Tavasoli, Reza Masumi, Mostafa Taghiyareh, Fattaneh University of Tehran Department of Computer Engineering Tehran Iran University of South Carolina Department of Computer Science and Engineering Columbia United States Sharif University of Technology Department of Computer Engineering Tehran Iran

ISBN: (纸本)9798350356250

Large Language Models (LLMs) are increasingly utilized in educational settings, raising questions about their efficacy in standardized testing contexts. This study evaluates the performance of popular LLMs, including GPT-4o, Claude 3.5 Sonnet, Gemini 1.5 Flash, Llama-3.1-70B, Mistral Large 2, DeepSeek-V2, and Gemma-2-27B, in answering data structure and algorithm design questions from the Iranian university entrance exams for master's programs in computer science and information technology. The research analyzes the accuracy of responses, the length of answers, required reading time, and vocabulary levels across the 2022,2023, and 2024 exams. Questions were categorized into five main areas: Algorithm Analysis and Complexity, Sorting and Searching, graph algorithms, Data Structures, and Advanced Topics and NP-completeness. The study compares the LLMs' performance in both Persian and English contexts, providing a comprehensive evaluation of their capabilities and limitations in this domain. Results indicate that GPT-4o achieved the highest average accuracy 75.0%followed by Claude 3.5 Sonnet (67.2%) and Mistral Large 2 (64.1%). The majority of the models performed better on English questions compared to Persian, with GPT-4o showing the largest performance gap (81.3% vs 68.8%). The findings offer insights into the practical applications of LLMs in educational assessments and contribute to the ongoing discourse on the role of AI in academia, particularly in non-English speaking regions. © 2024 IEEE.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Determining Sugiyama Topology with Model Order 32

Determining Sugiyama Topology with Model Order

引用

32nd International Symposium on graph Drawing and Network Visualization, GD 2024

作者： Domrös, Sören Von Hanxleden, Reinhard Department of Computer Science Kiel University Germany

ISBN: (纸本)9783959773430

Traditional implementations of the Sugiyama algorithm optimize aesthetic criteria such as the number of backward edges, edge length, or edge crossings. If we, however, utilize the model order, as provided e. g. by a textual graph input file, we can determine the topology of a Sugiyama layout in a one-pass algorithm while controlling the secondary notation and with it the intention expressed by the underlying model, which typically cannot be captured by layout algorithms. © Sören Domrös and Reinhard von Hanxleden.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Intelligent Substation SCD File Verification and Differentiated Display Method for Security Control 11

Intelligent Substation SCD File Verification and Differentia...

引用

11th China International Conference on Electricity Distribution, CICED 2024

作者： Liu, Shidan Yu, Weiguo Cheng, Jiafu Li, Jin Liu, Wei Tan, Qian Power Dispatching Control Center Guangdong Power Grid Co. Ltd. Guangzhou China Cyg Sunri Co. Ltd. Shenzhen China

ISBN: (纸本)9798350368345

A security oriented intelligent substation SCD file verification and differentiated display method is proposed to address the issues of low efficiency and high error rates in traditional manual verification methods. Firstly, use Levenshtein distance algorithm to verify the parsed substation configuration description (SCD) text. Then, based on the knowledge graph, the verified and error free SCD file is visualized and displayed. Finally, the RKR-GST algorithm is used to compare different versions of SCD files and visually display their differentiated details. Based on the SCD file of a 220kV intelligent substation, experimental analysis is conducted on the proposed method. The results shows that the verification accuracy mostly exceeds 95%, and the differences between SCD file versions are visually displayed, which can be well applied to the safety control of intelligent substations. © 2024 IEEE.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Systematic study of topology control methods and routing techniques in wireless sensor networks

引用

PEER-TO-PEER NETWORKING AND APPLICATIONS 2022年第4期15卷 1862-1922页

作者： Kavra, Radhika Gupta, Anjana Kansal, Sangita Delhi Technol Univ Dept Appl Math Bawana Rd Delhi India

Emergence of applications of wireless sensor networks in various fields over time requires to acknowledge existing solutions which have been proposed in history to overcome various challenges/ issues related to topology formation and routing of sensing data among the sensors. Sometime data transmission requires topology establishment or its awareness and sometime it does not. In order to obtain optimal routing topology or an optimal route according to some desired aim, a wide range of topology control methods and routing techniques/protocols come into sight. This article is the very first attempt in offering the collective and combined review on unexplored topology control methods and routing techniques, year-wise. Presenting a comprehensive study of various energy efficient topology control methods involving the graph based methodologies, explicitly designed interference models and related algorithms which have not been covered in previous year survey papers and the detail review on most efficient network structure based classical hierarchical routing protocols, topology aware particle swarm optimization and ant colony optimization based routing techniques in both static and mobile wireless sensor networks. However, the mentioned techniques don't cooperate delay sensitive routing or timely data delivery, for this purpose, we additionally provide a detail review on delay-sensitive real-time routing protocols in this survey paper. Analysis of each technique has been put forth year-wise by mentioning contribution made by the proposed work, detail of methodology opted, merits and demerits. A brief comparative study among the existing techniques, discussion about the research gaps and persisting issues along with direction of future work have also been provided.

关键词： Wireless sensor networks (WSNs) Topology graph algorithms Optimization techniques alpha-approximate solution Time complexity

来源：评论

学校读者我要写书评

暂无评论

Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n) 64

Path-Reporting Distance Oracles with Logarithmic Stretch and...

引用

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

作者： Elkin, Michael Shabat, Idan Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

ISBN: (纸本)9798350318944

Given an n-vertex undirected graph G = (V, E, w), and a parameter k >= 1, a path-reporting distance oracle (or PRDO) is a data structure of size S(n, k), that given a query (u, v) is an element of V-2, returns an f(k)-approximate shortest u - v path P in G within time q(k) + O(|P|). Here S(n, k), f(k) and q(k) are arbitrary (hopefully slowly-growing) functions. A distance oracle that only returns an approximate estimate d(u, v) of the distance d(G)(u, v) between the queried vertices is called a nonpath-reporting distance oracle. A landmark PRDO due to Thorup and Zwick [56] has S(n, k) = O(k . n(1+ 1/k)), f(k) = 2k - 1 and q(k) = O(k). Wulff-Nilsen [59] devised an improved query algorithm for this oracle with q(k) = O(log k). The size of this oracle is Omega(n log n) for all k. Elkin and Pettie [30] devised a PRDO with S(n, k) = O(log k . n(1+ 1/k)), f(k) = O(k(log4/3) 7) and q(k) = O(log k). Neiman and Shabat [46] recently devised an improved PRDO with S(n, k) = O(n(1+ 1/k)), f(k) = O(k(log4/3) 4) and q(k) = O(log k). These oracles (of [30], [46]) can be much sparser than O(n log n) (the oracle of [46] can have linear size), but their stretch is polynomially larger than the optimal bound of 2k - 1. On the other hand, a long line of non-pathreporting distance oracles culminated in a celebrated result by Chechik [14], in which S(n, k) = O(n(1+ 1/k)), f(k) = 2k - 1 and q(k) = O(1). In this paper we make a dramatic progress in bridging the gap between path-reporting and non-path-reporting distance oracles. In particular, we devise a PRDO with size S(n, k) = O(inverted right perpendicular *** log n/log n inverted left perpendicular . n(1+ 1/k) ), stretch f(k) = O(k) and query time q(k) = O(log inverted right perpendicular *** log n/log n inverted left perpendicular). As inverted right perpendicular *** log n/log n inverted left perpendicular = O(log k) for k <= log n, its size is always at most O(log k center dot n(1+ 1/k)), and its query time is O(log log k). More

关键词： graph algorithms shortest paths distance oracles

来源：评论

学校读者我要写书评

暂无评论

New algorithms for All Pairs Approximate Shortest Paths 2023

New Algorithms for All Pairs Approximate Shortest Paths

引用

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

作者： Roditty, Liam Bar Ilan Univ Ramat Gan Israel

Let G = (V, E) be an unweighted undirected graph with n vertices and (min{n(3/2)m(1/2), n(7/3)})-time algorithm that computes estimated distances with an additive approximation of 2 without using Fast Matrix Multipli... 详细信息

ISBN: (纸本)9781450399135

Let G = (V, E) be an unweighted undirected graph with n vertices and < edges. Dor, Halperin, and Zwick [FOCS 1996, SICOMP 2000] presented an <(O)over tilde> (min{n(3/2)m(1/2), n(7/3)})-time algorithm that computes estimated distances with an additive approximation of 2 without using Fast Matrix Multiplication (FMM). Recently, Deng, Kirkpatrick, Rong, V. Williams and Zhong [ICALP 2022] improved the running time for dense graphs to (O) over tilde (n(2.29))-time, using FMM, where an exact solution can be computed with FMM in (k) over tilde (n(omega)) time (omega < 2.37286) using Seidel's algorithm. Since an additive 2 approximation is also a multiplicative 2 approximation, computing an additive 2 approximation is at least as hard as computing a multiplicative 2 approximation. Thus, computing a multiplicative 2 approximation might be an easier problem. Nevertheless, more than two decades after the paper of Dor, Halperin, and Zwick was first published, no faster algorithm for computing multiplicative 2 approximation in dense graphs is known, rather then simply computing an additive 2 approximation. In this paper we present faster algorithms for computing a multiplicative 2 approximation without FMM. We show that in (O) over tilde (min{n(1/2)m, n(9/4)}) time it is possible to compute a multiplicative 2 approximation. For distances at least 4 we can get an even faster algorithm that in (O) over tilde (min {n(7/4)m(1/4), n(11/5)}) expected time computes a multiplicative 2 approximation. Our algorithms are obtained by a combination of new ideas that take advantage of a careful new case analysis of the additive approximation algorithms of Dor, Halperin, and Zwick. More specifically, one of the main technical contributions we made is an analysis of the algorithm of Dor, Halperin, and Zwick that reveals certain cases in which their algorithm produces improved additive approximations without any modification. This analysis provides a full characterization of the instances for wh

关键词： graph algorithms shortest paths all pairs approximate shortest paths

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：