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

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

作者： Bar-Noy, Amotz Böhnlein, Toni Peleg, David Ran, Yingli Rawitz, Dror NY United States Huawei Zurich Switzerland Weizmann Institute of Science Rehovot Israel Bar Ilan University Ramat-Gan Israel

ISBN: (纸本)9783959773355

A sequence d = (d1, d2, . . ., dn) of positive integers is graphic if it is the degree sequence of some simple graph G, and planaric if it is the degree sequence of some simple planar graph G. It is known that if ∑ d ≤ 2n − 2, then d has a realization by a forest, hence it is trivially planaric. In this paper, we seek bounds on ∑ d that guarantee that if d is graphic then it is also planaric. We show that this holds true when ∑ d ≤ 4n − 4 − 2ω1, where ω1 is the number of 1’s in d. Conversely, we show that there are graphic sequences with ∑ d = 4n − 2ω1 that are non-planaric. For the case ω1 = 0, we show that d is planaric when ∑ d ≤ 4n − 4. Conversely, we show that there is a graphic sequence with ∑ d = 4n − 2 that is non-planaric. In fact, when ∑ d ≤ 4n − 6 − 2ω1, d can be realized by a graph with a 2-page book embedding. © Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel Katz Centrality On Evolving graphs 31

Parallel Katz Centrality On Evolving Graphs

引用

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

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

ISBN: (纸本)9798331509118

Katz centrality measures a node’s influence within a network, considering the total number of walks between pairs of nodes rather than solely the shortest paths. This paper presents an algorithm for dynamically updating Katz centrality scores as the underlying graph evolves. Our method employs a frontier-based breadth-first search (BFS) to efficiently derive updated Katz scores in dynamic graphs. Notably, our algorithm accommodates node insertions and deletions, addressing a significant limitation of current state-of-the-art methods. © 2024 IEEE

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Eternal Connected Vertex Cover Problem in graphs: Complexity and algorithms 10th

Eternal Connected Vertex Cover Problem in Graphs: Complexity...

引用

10th International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Paul, Kaustav Pandey, Arti Indian Inst Technol Ropar Dept Math Nangal Rd Rupnagar 140001 Punjab India

ISBN: (纸本)9783031522123;9783031522130

A variation of the vertex cover problem is the eternal vertex cover problem. This is a two-player (attacker and defender) game, where the defender must allocate guards at specific vertices in order for those vertices to form a vertex cover. The attacker can attack one edge at a time. The defender must move the guards along the edges so that at least one guard passes through the attacked edge (guard moves from one end point of the attacked edge to the another end point), and the new configuration still acts as a vertex cover. If the defender is unable to make such a maneuver, the attacker prevails. If a strategy for defending the graph against any infinite series of attacks emerges, the defender wins. The eternal vertex cover problem is to find the smallest number of guards with which the defender can develop a successful strategy. The same problem is referred as the eternal connected vertex cover problem if the following additional requirement is added: underlying vertices of each defensive configuration form a connected vertex cover. The smallest number of guards that can be used to create a successful defensive strategy, in this case, is known as the eternal connected vertex cover number and is denoted by the ecvc(G). The decision version of the eternal connected vertex cover problem is NP-hard for general graphs and it also remains NP-hard for bipartite graphs. In this paper, we proved that the problem is polynomial-time solvable for chain graphs and cographs. In addition, we proved that the problem is NP-hard for Hamiltonian graphs, and proposed a polynomial-time algorithm to compute eternal connected vertex cover number for Mycielskian of a given Hamiltonian graph.

关键词： Eternal Connected vertex cover Chain graphs Hamiltonian graphs Mycielskian Cographs Distance-hereditary graphs graph algorithms

来源：评论

学校读者我要写书评

暂无评论

The Modified Genetic Algorithm for Solving the Traveling Salesman Problem 28th

The Modified Genetic Algorithm for Solving the Traveling Sal...

引用

2024 International Conference Automation

作者： Solohubov, Illia Moroz, Artur Oliinyk, Andrii Subbotin, Sergey Skrupsky, Stepan Natl Univ Zaporizhzhya Politech Zaporizhzhya Ukraine

ISBN: (纸本)9783031782657;9783031782664

The Traveling Salesman Problem is one of the most relevant challenges today, as the need to solve it arises in various fields. However, there is no clear algorithm for its solution. It falls within the realm of NP-complete problems and is optimization-oriented. While it is assumed that the solution to these problems involves exhaustive search, in practice, various algorithms and approaches are often used to reduce the volume of analyzed solutions, aiming to find a way to solve the problem without exhaustive search. This includes methods like branch and bound to expedite the search or artificial intelligence approaches such as the ant colony algorithm and genetic algorithms to accelerate the process while achieving the closest possible solution. Genetic methods are one of the most powerful tools for solving such tasks. These algorithms model evolutionary processes, which, thanks to the basic principles of evolution, allow finding better solutions. This approach allows representing the task as a certain evolutionary process. It is based on the fact that from the very beginning, a certain set of solutions is chosen, and they start competing with each other. Each solution represents an individual, and a set of its solutions represents a "gene". Each of these genes during the algorithm's operation can evolve, adapt, or mutate according to the rules of the environment. In the end, only the strongest genes should remain, which will be the approximate optimal solution. A characteristic of these algorithms is that each implementation can be unique. An important task in building algorithms is precisely the optimization of their parameters, as well as choosing the right approach to some of its stages, where only the best of them will remain in the end. This methodology not only allows finding approximately optimal solutions but also provides flexibility and adaptability for various requirements and constraints.

关键词： Algorithmic Modification Genetic algorithm graph algorithms Mutation Coefficient Optimization TSP Traveling Salesman Problem

来源：评论

学校读者我要写书评

暂无评论

Ant Colony Optimization Based Algorithm for Test Path Generation Problem with Negative Constraints 24

Ant Colony Optimization Based Algorithm for Test Path Genera...

引用

24th IEEE International Conference on Software Quality, Reliability and Security (QRS)

作者： Klima, Matej Bures, Miroslav Blaha, Martin Czech Tech Univ Fac Elect Engn Dept Comp Sci Syst Testing Intelligent Lab STILL Prague Czech Republic Univ Def Fac Mil Leadership Dept Fire Support Brno Czech Republic

ISBN: (纸本)9798350365634

Path-based testing is an established method for creating test cases comprising sequences of steps executed in a System Under Test (SUT). Several algorithms for generating the test sequences (paths) that satisfy various test coverage criteria determining their properties are published in the literature. However, existing path-based testing techniques have limited applicability in numerous practical cases, such as when executing a particular test step in the test further excludes the execution of another test step. More complex exclusion requirements (further denoted negative constraints) exist in real systems, depending on the number of executions of a particular test step. In the paper, we discuss two possible negative constraints, namely, (1) the complete exclusion of a step as a consequence of the execution of a particular previous step and (2) the requirement to include a particular step maximally once in one test path, when another step was executed previously. We present a novel ant-colony-optimization (ACO) principle-based algorithm, accepting a SUT model based and a set of negative constraints, and computing a set of test paths while maximizing edge coverage and satisfying the given set of negative constraints. We compare the results of the ACO-based algorithm with those returned by a baseline, an alternative algorithm that excludes specific test paths from a set of test paths satisfying edge coverage, and, for reference, with results returned by an algorithm that generates test paths that satisfy edge coverage. Evaluated on 152 problem instances, the presented ACO-based algorithm outperformed the baseline in the average length of test paths (representing the testing costs) lower by 32.62%. Also, the ratio of edge coverage satisfaction in the set of test paths computed by the ACO-based algorithm is better by 3.41% compared to the baseline.

关键词： Model-based Testing Path-based Testing Ant Colony Optimization Test Automation graph algorithms Negative Constraints

来源：评论

学校读者我要写书评

暂无评论

Listing 6-Cycles in Sparse graphs 16

Listing 6-Cycles in Sparse Graphs

引用

16th Innovations in Theoretical Computer Science Conference, ITCS 2025

作者： Williams, Virginia Vassilevska Westover, Alek MIT CambridgeMA United States

ISBN: (纸本)9783959773614

This work considers the problem of output-sensitive listing of occurrences of 2k-cycles for fixed constant k ≥ 2 in an undirected host graph with m edges and t 2k-cycles. Recent work of Jin and Xu (and independently Abboud, Khoury, Leibowitz, and Safier) [STOC 2023] gives an O(m4/3 + t) time algorithm for listing 4-cycles, and recent work by Jin, Vassilevska Williams and Zhou [SOSA 2024] gives an Oe(n2 + t) time algorithm for listing 6-cycles in n node graphs. We focus on resolving the next natural question: obtaining listing algorithms for 6-cycles in the sparse setting, i.e., in terms of m rather than n. Previously, the best known result here is the better of Jin, Vassilevska Williams and Zhou’s Oe(n2 + t) algorithm and Alon, Yuster and Zwick’s O(m5/3 + t) algorithm. We give an algorithm for listing 6-cycles with running time Oe(m1.6 + t). Our algorithm is a natural extension of Dahlgaard, Knudsen and Stöckel’s [STOC 2017] algorithm for detecting a 2k-cycle. Our main technical contribution is the analysis of the algorithm which involves a type of "supersaturation" lemma relating the number of 2k-cycles in a bipartite graph to the sizes of the parts in the bipartition and the number of edges. We also give a simplified analysis of Dahlgaard, Knudsen and Stöckel’s 2k-cycle detection algorithm (with a small polylogarithmic increase in the running time), which is helpful in analyzing our listing algorithm. © Virginia Vassilevska Williams and Alek Westover.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Learning-Augmented Streaming algorithms for Approximating MAX-CUT 16

Learning-Augmented Streaming Algorithms for Approximating MA...

引用

16th Innovations in Theoretical Computer Science Conference, ITCS 2025

作者： Dong, Yinhao Peng, Pan Vakilian, Ali School of Computer Science and Technology University of Science and Technology of China Hefei China IL United States

ISBN: (纸本)9783959773614

We study learning-augmented streaming algorithms for estimating the value of MAX-CUT in a graph. In the classical streaming model, while a 1/2-approximation for estimating the value of MAX-CUT can be trivially achieved with O(1) words of space, Kapralov and Krachun [STOC’19] showed that this is essentially the best possible: for any ϵ > 0, any (randomized) single-pass streaming algorithm that achieves an approximation ratio of at least 1/2 + ϵ requires Ω(n/2poly(1/ϵ)) space. We show that it is possible to surpass the 1/2-approximation barrier using just O(1) words of space by leveraging a (machine learned) oracle. Specifically, we consider streaming algorithms that are equipped with an ϵ-accurate oracle that for each vertex in the graph, returns its correct label in {-1, +1}, corresponding to an optimal MAX-CUT solution in the graph, with some probability 1/2 + ϵ, and the incorrect label otherwise. Within this framework, we present a single-pass algorithm that approximates the value of MAX-CUT to within a factor of 1/2 + Ω(ϵ2) with probability at least 2/3 for insertion-only streams, using only poly(1/ϵ) words of space. We also extend our algorithm to fully dynamic streams while maintaining a space complexity of poly(1/ϵ, log n) words. © Yinhao Dong, Pan Peng, and Ali Vakilian.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster (Δ+1)-Edge Coloring: Breaking the m√n Time Barrier 65

Faster (Δ+1)-Edge Coloring: Breaking the m√n Time Barrier

引用

65th Symposium on Foundations of Computer Science

作者： Bhattacharya, Sayan Carmon, Din Costa, Martin Solomon, Shay Zhang, Tianyi Univ Warwick Coventry W Midlands England Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9798331516758;9798331516741

Vizing's theorem states that any n-vertex m-edge graph of maximum degree. can be edge colored using at most Delta + 1 different colors [Diskret. Analiz, '64]. Vizing's original proof is algorithmic and shows that such an edge coloring can be found in (O) over tilde (mn) time. This was subsequently improved to (O) over tilde (m root n), independently by Arjomandi [1982] and by Gabow et al. [1985]. In this paper we present an algorithm that computes such an edge coloring in (O) over tilde (mn(1/3)) time, giving the first polynomial improvement for this fundamental problem in over 40 years.

关键词： graph algorithms edge coloring Vizing's theorem

来源：评论

学校读者我要写书评

暂无评论

Partial Domination in Some Geometric Intersection graphs 11th

Partial Domination in Some Geometric Intersection Graphs

引用

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

作者： Dutta, Madhura Maheshwari, Anil Nandy, Subhas C. TCG CREST Kolkata700091 India School of Computer Science Carleton University Ottawa Canada Ramkrishna Mission Vivekananda Centenary College Kolkata700118 India Ghaziabad201002 India

ISBN: (纸本)9783031834370

Partial domination problem is a generalization of the minimum dominating set problem on graphs. Here, instead of dominating all the nodes, one asks to dominate at least a fraction of the nodes of the given graph by choosing a subset of nodes of minimum size. For any real number α∈(0,1], α-partial domination problem can be proved to be NP-complete for general graphs. In this paper, we define the maximum dominating k-set of a graph which is polynomially transformable to the partial domination problem. We propose polynomial time algorithms for the maximum dominating k-set problem for some geometric intersection graphs, namely, interval graphs and unit square intersection graphs where the given squares are intersected by the straight line L:y=-x. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A segment-graph algorithm for two-objective wireless spectrum allocation in cognitive networks

引用

COMPUTER COMMUNICATIONS 2021年 165卷 97-104页

作者： Gao, Jian Guo, Chubing Pu, Mingfeng Zhang, Xin Li, Ying Wu, Jianshe Yu, Xin Xidian Univ Sch Artificial Intelligence Xian 710071 Peoples R China Xidian Univ Joint Lab Artificial Intelligence China Elect Technol Grp Corp Res Inst 20 Xian 710068 Peoples R China Sci & Technol Elect Informat Control Lab Qingdao Peoples R China

A segment-graph algorithm is provided for wireless spectrum allocation in cognitive networks based on the cooperation of the secondary users, which aim to maximize the utilization of the limited spectrum bands and minimize the total cost of all the secondary users to buy (or lease) the spectrum bands. The segment-graph of the complement graph of the original interference graph is defined. The proposed segment-graph algorithm is based on finding the complete subgraph of the segment-graph repeatedly. It is proved that the proposed algorithm always obtains the optimal solution if one of the segment-graphs is complete in each iteration. In general cases, the proposed algorithm dramatically reduces the total cost of all the secondary users. Comparative simulations agree with the theoretical results obtained.

关键词： Constrained optimization graph algorithms Network communication Wireless communication

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：