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

作者： Ott, Lukáš Brno University of Technology

Bakalářská práce je zaměřena na seznámení se s teorií grafů a grafových algoritmů pro hledání nejkratší cesty a následnou implementací získaných p... 详细信息

Bakalářská práce je zaměřena na seznámení se s teorií grafů a grafových algoritmů pro hledání nejkratší cesty a následnou implementací získaných poznatků do programu MS Excel 2003 s využitím jazyka VBA. Teorie grafů nás provází vším, od elementárních problémů, až po složité úkony a pokud budeme schopni pochopit základní poznatky uvedené v této práci, budeme schopni je následně využít také v praxi.

关键词： Graf grafový algoritmus cesta minimální kostra grafu VBA praktické využití. graph graph algorithm path minimum spanning tree VBA practical use. Text

来源：评论

学校读者我要写书评

暂无评论

New Bounds for Combinatorial Problems and Quasi-Gray Codes

New Bounds for Combinatorial Problems and Quasi-Gray Codes

引用

作者： Das, Debarati Charles University of Prague

This thesis consists of two parts. In part I, a group of combinatorial problems pertaining to strings, boolean matrices and graphs is studied. For given two strings x and y, their edit distance is the minimum number of character insertions, deletions and substitutions required to convert x into y. In this thesis we provide an algorithm that computes a constant approximation of edit distance in truly sub-quadratic time. Based on the provided ideas, we construct a separate sub- quadratic time algorithm that can find an occurrence of a pattern P in a given text T while allowing a few edit errors. Afterwards we study the boolean matrix multiplication (BMM) problem where given two boolean matrices, the aim is to find their product over boolean semi-ring. For this problem, we present two combinatorial models and show in these models BMM requires Ω(n3 /2O( √ log n) ) and Ω(n7/3 /2O( √ log n) ) work respectively. Furthermore, we also give a construction of a sparse sub-graph that preserves the distance between a designated source and any other vertex as long as the total weight increment of all the edges is bounded by some constant. In part II, we study the efficient construction of quasi-Gray codes. We give a construction of space optimal quasi-Gray codes over odd sized alphabets with read complexity 4...

关键词： Boolean matrix multiplication Combinatorial lower bounds Edit distance Pattern matching graph algorithm Quasi-Gray code

来源：评论

学校读者我要写书评

暂无评论

Computational results for Gaussian moat problem

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2005年第5期E88A卷 1267-1273页

作者： Tsuchimura, N Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138656 Japan

"Can one walk to infinity on Gaussian primes taking steps of bounded length?" We adopted computational techniques to probe into this open problem. We propose an efficient method to search for the farthest point reachable from the origin, which can be parallelized easily, and have confirmed the existence of a moat of width k = root 36, whereas the best previous result was k = root 26 due to Gethner et al. The amount of computation needed for k = root 36 is about 5000 times larger than that for k = root 26. A refinement of Vardi's estimate for the farthest distance reachable from the origin is proposed. The proposed estimate incorporates discreteness into Vardi's that is based on percolation theory.

关键词： graph algorithm Gaussian prime parallel computing

来源：评论

学校读者我要写书评

暂无评论

Approximability of the minimum maximal matching problem in planar graphs

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2003年第12期E86A卷 3251-3258页

作者： Nagamochi, H Nishida, Y Ibaraki, T Toyohashi Univ Technol Dept Informat & Comp Sci Toyohashi Aichi 4418580 Japan Japan Res Inst Ltd Osaka 5500013 Japan Kyoto Univ Fac Informat Dept Appl Math & Phys Kyoto 6068501 Japan

Given an edge-weighted graph G, the minimum maximal matching problem asks to find a minimum weight maximal matching. The problem is known to be NP-hard even if the graph is planar and unweighted. In this paper, we consider the problem in planar graphs. First, we prove a strong inapproximability for the problem in weighted planar graphs. Second, in contrast with the first result, we show that a polynomial time approximation scheme (PTAS) for the problem in unweighted planar graphs can be obtained by a divide-and-conquer method based on the planar separator theorem. For a given epsilon > 0, our scheme delivers in O(n log n + alphaepsilon(1/2) epsilon(-1)n) time a solution with size at most (1 + epsilon) times the optimal value, where n is the number of vertices in G and a is a constant number.

关键词： graph algorithm approximation algorithm matching planar graph separator

来源：评论

学校读者我要写书评

暂无评论

Asset management optimization in smart grids

引用

ENVIRONMENTAL PROGRESS & SUSTAINABLE ENERGY 2022年第5期41卷 e13824-e13824页

作者： Dashti, Reza Hosseini, Amirpouya Iran Univ Sci & Technol Sch Adv Technol Tehran Iran

Electricity distribution companies manage financial resources to maximize profits. While the stability of the electricity distribution system depends on the efficiency of the resources used by this system. The regulator is responsible for balancing and aligning the stability of the electricity industry with the profits of electricity distribution companies, which does so by adjusting penalty indices and service rates. This article investigates the management indicators of the electricity distribution industry and how to spend each of them is studied by electricity distribution companies and provides a model that can guide the optimization of the division of financial resources and investment between the indicators. Adjust indicators for regulators to align the benefits and profits of electricity distribution companies with the stability of the electricity distribution system. The implementation of this model was observed in Bushehr Electricity Distribution Company and increased the efficiency percentage.

关键词： asset efficiency distribution utility graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Enumerating Trillion Subgraphs On Distributed Systems

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2018年第6期12卷 71-71页

作者： Park, Ha-Myung Silvestri, Francesco Pagh, Rasmus Chung, Chin-Wan Myaeng, Sung-Hyon Kang, U. Korea Adv Inst Sci & Technol Daejeon South Korea Univ Padua Padua Italy IT Univ Copenhagen Copenhagen Denmark Chongqing Univ Technol Chongqing Peoples R China Seoul Natl Univ Seoul South Korea

How can we find patterns from an enormous graph with billions of vertices and edges? The subgraph enumeration, which is to find patterns from a graph, is an important task for graph data analysis with many applications, including analyzing the social network evolution, measuring the significance of motifs in biological networks, observing the dynamics of Internet, and so on. Especially, the triangle enumeration, a special case of the subgraph enumeration, where the pattern is a triangle, has many applications such as identifying suspicious users in social networks, detecting web spams, and finding communities. However, recent networks are so large that most of the previous algorithms fail to process them. Recently, several MapReduce algorithms have been proposed to address such large networks;however, they suffer from the massive shuffled data resulting in a very long processing time. In this article, we propose scalable methods for enumerating trillion subgraphs on distributed systems. We first propose PTE (Pre-partitioned Triangle Enumeration), a new distributed algorithm for enumerating triangles in enormous graphs by resolving the structural inefficiency of the previous MapReduce algorithms. PTE enumerates trillions of triangles in a billion scale graph by decreasing three factors: the amount of shuffled data, total work, and network read. We also propose PSE (Pre-partitioned Subgraph Enumeration), a generalized version of PTE for enumerating subgraphs that match an arbitrary query graph. Experimental results show that PTE provides 79 times faster performance than recent distributed algorithms on real-world graphs, and succeeds in enumerating more than 3 trillion triangles on the ClueWeb12 graph with 6.3 billion vertices and 72 billion edges. Furthermore, PSE successfully enumerates 265 trillion clique subgraphs with 4 vertices from a subdomain hyperlink network, showing 47 times faster performance than the state of the art distributed subgraph enumeration algor

关键词： Triangle enumeration subgraph enumeration big data graph algorithm scalable algorithm distributed algorithm network analysis

来源：评论

学校读者我要写书评

暂无评论

New algorithms for a simple measure of network partitioning

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期957卷

作者： Zhao, Xueyang Yan, Binghao Zhang, Peng Shandong Univ Sch Software Jinan 250101 Shandong Peoples R China

Partitioning a network into k pieces is a fundamental problem in network science. A simple measure of partitioning a network is provided by the Max k-Uncut problem. Given an nvertex undirected graph G with nonnegative weights defined on edges, and a positive integer k, the Max k-Uncut problem asks to find a k-partition of the vertices of G to maximize the total weight of edges that are not in the cut. This problem is the complement of the classic Min k-Cut problem, and has close relation to many combinatorial optimization problems, including the famous Densest k-Subgraph problem. In this paper, we propose a greedy approximation algorithm for the Max k-Uncut problem with performance ratio 1 - 2(k-1) n . The algorithm is very simple, which consists of only k -1 min cut computations. The algorithm has fast running time O(kn2) and is hence implementable. The experimental results show that the algorithm has excellent practical performance. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Network partitioning graph algorithm Approximation algorithm Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

On

引用

SIAM Journal on Discrete Mathematics 2012年第4期26卷 1682-1708页

作者： Frédéric Maffray Grégory Morel

A graph is P5P5P_5-free when it does not contain a <span class

A graph is

P_{5}

$P_5$ -free when it does not contain a

关键词： graph algorithm structure theorem stability -free graphs 05C15 05C75 05C85

来源：评论

学校读者我要写书评

暂无评论

Exact values for three domination-like problems in circular and infinite grid graphs of small height

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2019年第3期21卷 1页

作者： Bouznif, M. Darlay, J. Moncel, J. Preissmann, M. A SIS St Etienne France Innovation24 Paris France Univ Toulouse CNRS LAAS Toulouse France Federat Rech Maths Modeler St Martin Dheres France CNRS G SCOP Grenoble France

In this paper we study three domination-like problems, namely identifying codes, locating-dominating codes, and locating-total-dominating codes. We are interested in finding the minimum cardinality of such codes in circular and infinite grid graphs of given height. We provide an alternate proof for already known results, as well as new results. These were obtained by a computer search based on a generic framework, that we developed earlier, for the search of a minimum labeling satisfying a pseudo-d-local property in rotagraphs.

关键词： graph algorithm identifying code locating-dominating code locating-total-dominating code grid

来源：评论

学校读者我要写书评

暂无评论

An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth

引用

THEORETICAL COMPUTER SCIENCE 2024年 990卷

作者： Baste, Julien Watel, Dimitri Univ Lille CNRS Cent Lille UMR 9189CRIStAL F-59000 Lille France ENSIIE 1 Sq Resistance F-91000 Evry France Telecom SudParis SAMOVAR 9 Rue Charles Fourier F-91000 Evry France

In this paper, we introduce a problem called MINIMUM SUBTREE PROBLEM WITH DEGREE WEIGHTS, or MTDW. This problem generalized covering tree problems like SPANNING TREE, STEINER TREE, MINIMUM BRANCH VERTICES, MINIMUM LEAF SPANNING TREE, or PRIZE COLLECTING STEINER TREE. It consists, given an undirected graph G = (V, E), a set of m + 1 mappings C-1, C-2,...,C-m, D : V x N -> Z, a set of m integers K-1, K-2,...,K-m is an element of Z and a positive integer l, in the search of a forest (T-1,T-2,...,T-l) containing l node-disjoint trees of G. Along with K-l, the mapping C-l defines a constraint that should be satisfied by the trees of the forest. For each tree T-l, it associates each node n of V to the score C-l (upsilon,dT(l)(upsilon)) where d(Tl) (upsilon) is the degree of upsilon in T-l (possibly 0 if the node is not in T-l). The sum Sigma(upsilon is an element of V) C-j(upsilon, d(Tt)(upsilon)) should not exceed K-j. In addition, the forest should minimize Sigma(l)(t=1) Sigma(upsilon is an element of V) D(upsilon,dT(l) (upsilon)). We proceed to a parameterized analysis of the MTDW problem with regard to four parameters that are the number of constraints m, the value l, the treewidth of the input graph G and Delta, the minimum degree above which all the constraints and D are constant (for every j is an element of[1,m], upsilon is an element of V and d >= Delta, C-j(upsilon,d) = C-j(upsilon,Delta), and D(upsilon,d) = D(upsilon,Delta)). For this problem, we provide a first dichotomy P versus NP-hard depending whether the previous parameters are fixed to be constant or not and a second dichotomy FPT versus W[1]-hard depending whether each of these parameters is constant, considered as a parameter, or disregard. As a side effect, we obtained parameterized algorithms, previously undescribed, for problems such that BUDGET STEINER TREE PROBLEM WITH PROFITS, MINIMUM BRANCH VERTICES, GENERALIZED BRANCH VERTICES, or k-BOTTLENECK STEINER TREE.

关键词： Fixed-parameter tractable algorithm graph algorithm Spanning tree problems Treewidth

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：