Relevant bibliographies by topics / Graph modification problem

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

Academic literature on the topic 'Graph modification problem'

Author: Grafiati
Published: 4 June 2021
Last updated: 2 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Graph modification problem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Graph modification problem"

1

Sritharan, R. "Graph modification problem for some classes of graphs." Journal of Discrete Algorithms 38-41 (May 2016): 32–37. http://dx.doi.org/10.1016/j.jda.2016.06.003.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Asahiro, Yuichi, Jesper Jansson, Eiji Miyano, Hirotaka Ono, and T. P. Sandhya. "Graph Orientation with Edge Modifications." International Journal of Foundations of Computer Science 32, no. 02 (January 30, 2021): 209–33. http://dx.doi.org/10.1142/s012905412150012x.

Full text
Abstract:
The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph [Formula: see text] of an input undirected graph [Formula: see text] such that either: (Type I) the number of edges in [Formula: see text] is minimized or maximized and [Formula: see text] can be oriented to satisfy some specified constraints on the vertices’ resulting outdegrees; or: (Type II) among all subgraphs or supergraphs of [Formula: see text] that can be constructed by deleting or inserting a fixed number of edges, [Formula: see text] admits an orientation optimizing some objective involving the vertices’ outdegrees. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) [Formula: see text]-DEL-MAX, [Formula: see text]-INS-MIN, [Formula: see text]-INS-MAX, and [Formula: see text]-DEL-MIN. In each of the eight problems, the input is a graph and the goal is to delete or insert edges so that the resulting graph has an orientation in which the maximum outdegree (taken over all vertices) is small or the minimum outdegree is large. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees.
APA, Harvard, Vancouver, ISO, and other styles
3

IVANOV, DENIS, and ALEXANDER SEMENOV. "TOPOLOGICAL APPROACH TO BLACKHOLES ANOMALY DETECTION IN DIRECTED NETWORKS." Computational nanotechnology 7, no. 2 (June 30, 2020): 49–57. http://dx.doi.org/10.33693/2313-223x-2020-7-2-49-57.

Full text
Abstract:
In this paper we consider the problem of finding a blackhole pattern in directed unweighted graphs. The problem statement is the same as in an original paper by scientists from University of New-Jersey published in 2010. The paper contributes to the special graph pattern matching, the work results can be used for anomaly detection in finances, natural disasters, urban analysis. This paper aims to propose a novel algorithm for blackhole mining, which would take into account inner structure of the “blackhole” pattern and utilize this knowledge for more efficient mining. This paper reviews previously published solutions and tests them on larger graphs containing up to 1 million of nodes. In particular, an iBlackhole algorithm and its Divide and Conquer modification iBlackholeDC are considered, their weak spots are highlighted and reviewed upon. Graph condensation is introduced as an efficient preprocessing for the problem. This paper provides theorems and definitions describing inner structure of the blackhole pattern. Based on the new theorems, a new approach to enumeration of candidates is introduced as well as rules and heuristics aiming for faster filtration of candidates: they utilize topological sorting of a graph and definition of a “special” node, which is also introduced in this paper. Special nodes properties are described. We propose a novel TopSortBH algorithm. It consists of the graph condensation, candidates enumeration and heuristics for candidates filtration. The algorithm is provided with modification called FastSkip, which allows for more aggressive filtering strategy in time-sensitive cases. All mentioned algorithms are implemented and tested on the IBM Power8 based system. Experimental results show efficiency of the condensation as graph preprocessing for the problem. Strong advantage in found blackholes count is demonstrated for TopSortBH in comparison to iBlackholeDC on RMAT, SSCA2 and UR graphs containing up to 1 million nodes.
APA, Harvard, Vancouver, ISO, and other styles
4

Skakalina, E. "APPLICATION OF ANT OPTIMIZATION ALGORITHMS IN THE SOLUTION OF THE ROUTING PROBLEM." Системи управління, навігації та зв’язку. Збірник наукових праць 6, no. 58 (December 28, 2019): 75–83. http://dx.doi.org/10.26906/sunz.2019.6.075.

Full text
Abstract:
The article discusses current issues of using evolutionary algorithms to solve the routing problem. Ant algorithms (MA), like most types of evolutionary algorithms, are based on the use of a population of potential solutions and are designed to solve combinatorial optimization problems, first of all, search for various paths on graphs. The cooperation between individuals (artificial ants) is implemented on the basis of stigmetry modeling. In addition, each agent, called artificial ant, is looking for a solution to the problem. Artificial ants consistently build a solution to the problem, moving around the graph, lay the pheromone and, when choosing a further section of the path, take into account the concentration of this enzyme. The higher the concentration of pheromone in the subsequent section, the greater the likelihood of its choice. Since MA is based on the movement of ants along some paths, MAs are effective, first of all, in solving problems that can be interpreted in the form of a graph. Computer experiments showed that the efficiency of MA increases with increasing dimension of the problem and for tasks on high-dimensional graphs they work faster than other evolutionary algorithms. Good results were also noted in solving non-stationary problems on graphs with a changing environment. In connection with this, the implementation of the meta - heuristic method is proposed as a modification of ant optimization algorithms. The scheme of the system is presented. A software product specification is also provided
APA, Harvard, Vancouver, ISO, and other styles
5

NASTOS, JAMES, and YONG GAO. "BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES." Discrete Mathematics, Algorithms and Applications 04, no. 01 (March 2012): 1250008. http://dx.doi.org/10.1142/s1793830912500085.

Full text
Abstract:
Many fixed-parameter tractable algorithms using a bounded search tree have been repeatedly improved, often by describing a larger number of branching rules involving an increasingly complex case analysis. We introduce a novel and general search strategy that branches on the forbidden subgraphs of a graph class relaxation. By using the class of P4-sparse graphs as the relaxed graph class, we obtain efficient bounded search tree algorithms for several parametrized deletion problems. We give the first non-trivial bounded search tree algorithms for the cograph edge-deletion problem and the trivially perfect edge-deletion problems. For the cograph vertex deletion problem, a refined analysis of the runtime of our simple bounded search algorithm gives a faster exponential factor than those algorithms designed with the help of complicated case distinctions and non-trivial running time analysis [R. Niedermeier and P. Rossmanith, An efficient fixed-parameter algorithm for 3-hitting set, J. Discrete Algorithms1(1) (2003) 89–102] and computer-aided branching rules [J. Gramm, J. Guo, F. Hüffner and R. Niedermeier, Automated generation of search tree algorithms for hard graph modification problems, Algorithmica39(4) (2004) 321–347].
APA, Harvard, Vancouver, ISO, and other styles
6

Zolotarev, I. A., and V. A. Rasskazova. "Modification of Algorithm of Directed Graph Paths Decomposition with Schedule." Моделирование и анализ данных 11, no. 2 (2021): 51–58. http://dx.doi.org/10.17759/mda.2021110203.

Full text
Abstract:
This study aims to refinement of the oriented graph paths decomposition algorithm. An additional constraint on the balance parameter is considered to take into account the locomotive departure schedule. Also new rule to compute Ns parameters is given. An example of the operation of the oriented graph paths decomposition algorithm with the schedule is given. The scientific and practical novelty of the work lies in a significant reduction in the dimension of the original problem, which is especially important in the conditions of transport networks of complex topology.
APA, Harvard, Vancouver, ISO, and other styles
7

Albijanic, Miloljub. "Some properties of convex functions." Filomat 31, no. 10 (2017): 3015–21. http://dx.doi.org/10.2298/fil1710015a.

Full text
Abstract:
We treat two problems on convex functions of one real variable. The first one is concerned with properties of tangent lines to the graph of a convex function and essentially is related to the questions on the first derivative (if it exists). The second problem is related to Schwarz?s derivative, in fact its upper limit modification. It gives an interesting characterization of convex functions. Let us recall the definition of a convex functions.
APA, Harvard, Vancouver, ISO, and other styles
8

Panić, Biljana, Nataša Kontrec, Mirko Vujošević, and Stefan Panić. "A Novel Approach for Determination of Reliability of Covering a Node from K Nodes." Symmetry 12, no. 9 (September 5, 2020): 1461. http://dx.doi.org/10.3390/sym12091461.

Full text
Abstract:
In this paper, a stochastic problem of multicenter location on a graph was formulated through the modification of the existing p-center problem to determine the location of a given number of facilities, to maximize the reliability of supplying the system. The system is represented by a graph whose nodes are the locations of demand and the potential facilities, while the weights of the arcs represent the reliability, i.e., the probability that an appropriate branch is available. First, k locations of facilities are randomly determined. Using a modified Dijkstra’s algorithm, the elementary path of maximal reliability for every demand node is determined. Then, a graph of all of elementary paths for demand node is formed. Finally, a new algorithm for calculating the reliability of covering a node from k nodes (k—covering reliability) was formulated.
APA, Harvard, Vancouver, ISO, and other styles
9

Karim, A., C. Sueur, and G. Dauphin-Tanguy. "Non-regular static state feedback for linear bond graph models." Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering 217, no. 2 (March 1, 2003): 61–71. http://dx.doi.org/10.1177/095965180321700201.

Full text
Abstract:
In this paper, non-regular static state feedback solutions of the row-by-row decoupling problem (RBRDP) with stability are investigated by the bond graph approach for the class of non-square linear models. More precisely, the aim is to study the problem of the non-regular static state feedback designing, firstly, when the model is not decouplable with a regular static state feedback and, secondly, when the model is decouplable with a regular static state feedback but not with stability. The bond graph methodology is used in order to characterize the structure of non-square models and the modification of the infinite structure that arises when a regular control law cannot exist. A new graphical methodology is proposed. Finally, when row-by-row decoupling with stability is possible for non-square bond graph models, a formal expression of the control is given using simultaneously the bond graph and the geometric approaches.
APA, Harvard, Vancouver, ISO, and other styles
10

Phillips, Charles, Kai Wang, Erich Baker, Jason Bubier, Elissa Chesler, and Michael Langston. "On Finding and Enumerating Maximal and Maximum k-Partite Cliques in k-Partite Graphs." Algorithms 12, no. 1 (January 15, 2019): 23. http://dx.doi.org/10.3390/a12010023.

Full text
Abstract:
Let k denote an integer greater than 2, let G denote a k-partite graph, and let S denote the set of all maximal k-partite cliques in G. Several open questions concerning the computation of S are resolved. A straightforward and highly-scalable modification to the classic recursive backtracking approach of Bron and Kerbosch is first described and shown to run in O(3n/3) time. A series of novel graph constructions is then used to prove that this bound is best possible in the sense that it matches an asymptotically tight upper limit on |S|. The task of identifying a vertex-maximum element of S is also considered and, in contrast with the k = 2 case, shown to be NP-hard for every k ≥ 3. A special class of k-partite graphs that arises in the context of functional genomics and other problem domains is studied as well and shown to be more readily solvable via a polynomial-time transformation to bipartite graphs. Applications, limitations, potentials for faster methods, heuristic approaches, and alternate formulations are also addressed.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Graph modification problem"

1

Perez, Anthony. "Algorithmes de noyau pour des problèmes d'édition de graphes et autres structures." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2011. http://tel.archives-ouvertes.fr/tel-00660089.

Full text
Abstract:
Dans le cadre de cette thèse, nous considérons la complexité paramétrée de problèmes NP- complets. Plus précisément, nous nous intéressons à l'existence d'algorithmes de noyau polynomiaux pour des problèmes d'édition de graphes et de relations. Nous introduisons en particulier la notion de branches, qui permet d'obtenir des algorithmes polynomiaux pour des problèmes d'édition de graphes lorsque la classe de graphes cible respecte une décomposition d'adjacence. Cette technique nous permet ainsi d'élaborer les premiers algorithmes de noyaux polynomiaux pour les problèmes CLOSEST 3-LEAF POWER, COGRAPH EDITION et PROPER INTERVAL COMPLETION. Concernant les problèmes d'édition de relations, nous étendons la notion de Conflict Packing, qui a déjà été utilisée dans quelques problèmes paramétrés et permet d'élaborer des algorithmes de noyau linéaires pour différents problèmes. Nous présentons un noyau linéaire pour le problème FEEDBACK ARC SET IN TOURNAMENTS, et adaptons les techniques utilisées pour obtenir un noyau linéaire pour le problème DENSE ROOTED TRIPLET INCONSISTENCY. Dans les deux cas, nos résultats améliorent la meilleure borne connue, à savoir un noyau quadratique. Finalement, nous appliquons cette tech- nique sur les problèmes DENSE BETWEENNESS et DENSE CIRCULAR ORDERING, obtenant à nouveau des noyaux linéaires, qui constituent les premiers algorithmes de noyau polynomiaux connus pour ces problèmes.
APA, Harvard, Vancouver, ISO, and other styles
2

Chen, Li-Hsuan, and 陳立軒. "Parameterized Algorithms for Cluster-Graph Modification Problems." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/fzz4yp.

Full text
Abstract:
博士
國立中正大學
資訊工程研究所
104
\emph{Graph clustering} is an important issue in computer science. In general, we are given a graph with edges between similar objects, and the goal is to group the similar objects into clusters. A theoretical approach asks for editing a graph into disjoint cliques. Due to the wide applications, there are many formulated problem definitions. In this study, we show parameterized algorithms for some of the graph modification problems. A 2-clustering problem in general asks for a 2-partition such that the number of edges between the 2-partition and the non-edges in the same partition are as ``small'' as possible. As in many optimization problems, we developed several algorithms for the most frequently used cost functions: min-sum, min-max, and min-sum of squares. For the $p$-clusterings problems, in which the vertex set is split into $p$ clusters, we developed some ways to make use of the additional parameter $p$ to obtain better results with multiple parameters. We study the vertex deletion version and design an efficient algorithm with multiple parameters.
APA, Harvard, Vancouver, ISO, and other styles
3

"Polynomial kernelisation of H-free edge modification problems." 2012. http://library.cuhk.edu.hk/record=b5549171.

Full text
Abstract:
關於有唯一禁子圖的改邊問題的多項式核心無H加/删/加删邊問題求是否可能加/删/加删至多k條邊於一圖使其無任何與H同構的誘導子圖。此乃計算機科學基本問題之一，其研究廣泛。此題對任意固定H為NP完全且固定參數可解。本文研究無H改邊問題之多項式核心；其存在視H之結構而定。之分類在當H為一圈，路徑或三聯通圖時則完全，當H為删一邊於完全圖之結果時則近完全，當H為樹時則部分此結果加強對無H改邊問題之認識。本文的思路與工具益未來研究，或有助於無H改邊問題多項式核心存在二分定理之發現。
The H-free edge completion (deletion, editing) problem asks whether it is possible to add to (delete from, add to and delete from) a graph at most k edges so that no induced sub graph isomorphic to H remains. These problems are fundamental in computer science and were studied extensively. They are NP-complete and fixed-parameter tractable for every fixed H.
In this thesis, we study polynomial kernels for H-free edge modification problems, as their existence depends on the structure of H. We characterise their existence completely when H is a path, cycle or 3-connected graph, almost completely when H is one edge short of a complete graph, and partially when H is a tree.
These results enhance our understanding of H-free edge modification problems significantly. Our ideas and tools can be useful to future studies and may lead eventually to a dichotomy theorem on the existence of polynomial kernels for H-free edge modification problems.
Detailed summary in vernacular field only.
Cai, Yufei.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2012.
Includes bibliographical references (leaves 97-99).
Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Abstracts also in Chinese.
Chapter 1 --- Preliminaries --- p.1
Chapter 1.1 --- Edge modification problems and kernelisation --- p.2
Chapter 1.2 --- Main results --- p.4
Chapter 1.3 --- The lack of polynomial kernels --- p.5
Chapter 1.4 --- Conventions and organisation --- p.8
Chapter 2 --- Component Design --- p.11
Chapter 2.1 --- Weighted satisficability on selective formulas --- p.12
Chapter 2.2 --- 4-cycle --- p.15
Chapter 2.3 --- The general scheme of component design --- p.20
Chapter 2.4 --- Applications --- p.26
Chapter 3 --- Local Alteration --- p.31
Chapter 3.1 --- Bigger forbidden subgraphs from smaller ones --- p.32
Chapter 3.2 --- Lifting the quarantine --- p.37
Chapter 4 --- Circuit Implementation --- p.43
Chapter 4.1 --- Monotone circuits --- p.44
Chapter 4.2 --- Centralisation --- p.45
Chapter 4.3 --- Implementation --- p.48
Chapter 5 --- Kernel for Diamond-Free Edge Deletion --- p.55
Chapter 5.1 --- Diamond-graphs --- p.56
Chapter 5.2 --- The invariant things --- p.59
Chapter 5.3 --- Correctness --- p.61
Chapter 5.4 --- Lockets --- p.64
Chapter 5.5 --- Representative systems of diamonds --- p.68
Chapter 5.6 --- Kernel size --- p.70
Chapter 6 --- Conclusions --- p.73
Chapter 6.1 --- 3-connected forbidden subgraphs --- p.74
Chapter 6.2 --- Cycles, paths and nearly complete graphs --- p.76
Chapter 6.3 --- Trees --- p.77
Chapter 6.4 --- Open problems --- p.79
Chapter A --- List of Trees --- p.81
Chapter B --- List of Problems --- p.83
Chapter C --- Glossary --- p.87
Chapter D --- Bibliography --- p.96
APA, Harvard, Vancouver, ISO, and other styles
4

Guo, Jiong [Verfasser]. "Algorithm design techniques for parameterized graph modification problems / von Jiong Guo." 2006. http://d-nb.info/981983995/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Graph modification problem"

1

Shamir, Ron, Roded Sharan, and Dekel Tsur. "Cluster Graph Modification Problems." In Graph-Theoretic Concepts in Computer Science, 379–90. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-36379-3_33.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Fomin, Fedor V., Saket Saurabh, and Neeldhara Misra. "Graph Modification Problems: A Modern Perspective." In Frontiers in Algorithmics, 3–6. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-19647-3_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Natanzon, Assaf, Ron Shamir, and Roded Sharan. "Complexity Classification of Some Edge Modification Problems." In Graph-Theoretic Concepts in Computer Science, 65–77. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. http://dx.doi.org/10.1007/3-540-46784-x_8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Komusiewicz, Christian, André Nichterlein, and Rolf Niedermeier. "Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics." In Graph-Theoretic Concepts in Computer Science, 3–15. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016. http://dx.doi.org/10.1007/978-3-662-53174-7_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Bessy, Stéphane, Christophe Paul, and Anthony Perez. "Polynomial Kernels for 3-Leaf Power Graph Modification Problems." In Lecture Notes in Computer Science, 72–82. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-10217-2_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Nastos, James, and Yong Gao. "A Novel Branching Strategy for Parameterized Graph Modification Problems." In Combinatorial Optimization and Applications, 332–46. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-17461-2_27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Gramm, Jens, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. "Automated Generation of Search Tree Algorithms for Graph Modification Problems." In Algorithms - ESA 2003, 642–53. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-39658-1_58.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Święcicka, Anna, Franciszek Seredyński, and Mariusz Jażdżyk. "Cellular Automata Approach to Scheduling Problem in Case of Modifications of a Program Graph." In Advances in Intelligent and Soft Computing, 155–66. Heidelberg: Physica-Verlag HD, 2001. http://dx.doi.org/10.1007/978-3-7908-1813-0_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Graph modification problem"

1

Toan, Tran Quoc, A. A. Sorokin, and Vo Thi Huyen Trang. "Using modification of visibility-graph in solving the problem of finding shortest path for robot." In 2017 International Siberian Conference on Control and Communications (SIBCON). IEEE, 2017. http://dx.doi.org/10.1109/sibcon.2017.7998564.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Савостин, Игорь, Igor' Savostin, Андрей Трубаков, and Andrey Trubakov. "The Combination of Morphological and Evolutionary Algorithms for Graph-based Pathfinding on Maps with Complex Topologies." In 29th International Conference on Computer Graphics, Image Processing and Computer Vision, Visualization Systems and the Virtual Environment GraphiCon'2019. Bryansk State Technical University, 2019. http://dx.doi.org/10.30987/graphicon-2019-2-300-303.

Full text
Abstract:
One of the difficult problems to solve has always been and still remains the problem of finding a path either in a graphic chart or a graphic maze of large size. The main problem is that traditional algorithms require a lot of time due to combinatorial complexity. At the same time, both classical algorithms based on the search of variants (such as Dijkstra's algorithm, A*, ARA*, D* lite), and stochastic algorithms (ant algorithm, genetic), alongside with algorithms based on morphology (wave) are not always able to achieve the goal. The article proposes a new modification of the path-finding algorithm, which is a hybrid of the following: the morphological operations on graphic chart approach and genetic algorithm having a useful property of elasticity in time. The experiments (both synthetic and real data) have shown the feasibility of the proposed idea and its comparison with the most commonly used algorithms of contemporaneity.
APA, Harvard, Vancouver, ISO, and other styles
3

Zvyagin, Petr, and Anna Voitkunskaia. "Model of Transit Transport in Arctic Based on Graph Algorithms." In ASME 2016 35th International Conference on Ocean, Offshore and Arctic Engineering. American Society of Mechanical Engineers, 2016. http://dx.doi.org/10.1115/omae2016-54439.

Full text
Abstract:
Transportation in Arctic seas is connected with variability of routes. Availability of those routes is depending on current environmental conditions. In the paper the algorithm for navigation system, which is intended to advice captain the most economically effective and less risky route with the presence of ice chart, is proposed. Smart navigation system for Arctic seas has specific: shortest ways can occur to be impassable or too risky. More long routes through free waters can finally take less fuel comparing to shorter, but covered with ice. Thus, economical profitability of operating in Arctic seas depends on effectiveness of route choosing. To make estimations about most effective route and its length, the method based on graph algorithms is presented in this paper. The ice chart is covered by the graph, which can have form of grid, with neighbor nodes connected by edges. In general, multiple parameters can be assigned to each edge — length, maximal ice thickness on the way, risk, etc. In this paper two separate cost functions are considered: first is responsible for travel expenses, and the second is responsible for ice passability on the route. To find most economically efficient route with minimal possible ice thickness on the way the method with graph modification and Dijkstra algorithm was used. This route provides Pareto-optimal solution for reduced version of the problem. The software, which implements the method, was built. The example of searching for least expensive and Pareto-optimal route is provided. Results are discussed.
APA, Harvard, Vancouver, ISO, and other styles
4

Venkatesan, Sibi, James K. Miller, Jeff Schneider, and Artur Dubrawski. "Scaling Active Search using Linear Similarity Functions." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/401.

Full text
Abstract:
Active Search has become an increasingly useful tool in information retrieval problems where the goal is to discover as many target elements as possible using only limited label queries. With the advent of big data, there is a growing emphasis on the scalability of such techniques to handle very large and very complex datasets. In this paper, we consider the problem of Active Search where we are given a similarity function between data points. We look at an algorithm introduced by Wang et al. [Wang et al., 2013] known as Active Search on Graphs and propose crucial modifications which allow it to scale significantly. Their approach selects points by minimizing an energy function over the graph induced by the similarity function on the data. Our modifications require the similarity function to be a dot-product between feature vectors of data points, equivalent to having a linear kernel for the adjacency matrix. With this, we are able to scale tremendously: for n data points, the original algorithm runs in O(n^2) time per iteration while ours runs in only O(nr + r^2) given r-dimensional features. We also describe a simple alternate approach using a weighted-neighbor predictor which also scales well. In our experiments, we show that our method is competitive with existing semi-supervised approaches. We also briefly discuss conditions under which our algorithm performs well.
APA, Harvard, Vancouver, ISO, and other styles
5

Posser, Gracieli, Ricardo Reis, and Sachin S. Sapatnekar. "Electromigration Aware Cell Design." In XXIX Concurso de Teses e Dissertações da SBC. Sociedade Brasileira de Computação - SBC, 2020. http://dx.doi.org/10.5753/ctd.2016.9144.

Full text
Abstract:
Electromigration (EM) in on-chip metal interconnects is a critical reliability failure mechanism in nanometer-scale technologies. This work addresses the problem of EM on signal interconnects and on Vdd and Vss rails within a standard cell. An approach for modeling and efficient characterization of cell-internal EM is developed, incorporating Joule heating effects. We also present a graph-based algorithm that computes the currents when the pin position is moved avoiding a new characterization for each pin position and consequently reducing considerable the characterization time. We use the cell lifetime analysis to determine the lifetime of large benchmark circuits, and show that these circuit lifetimes can be improved up to 80.95% by avoiding the critical output, Vdd, and Vss pin positions of the cells, using minor layout modifications.
APA, Harvard, Vancouver, ISO, and other styles
6

Medya, Sourav, Tiyani Ma, Arlei Silva, and Ambuj Singh. "A Game Theoretic Approach For Core Resilience." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/480.

Full text
Abstract:
K-cores are maximal induced subgraphs where all vertices have degree at least k. These dense patterns have applications in community detection, network visualization and protein function prediction. However, k-cores can be quite unstable to network modifications, which motivates the question: How resilient is the k-core structure of a network, such as the Web or Facebook, to edge deletions? We investigate this question from an algorithmic perspective. More specifically, we study the problem of computing a small set of edges for which the removal minimizes the k-core structure of a network. This paper provides a comprehensive characterization of the hardness of the k-core minimization problem (KCM), including innaproximability and parameterized complexity. Motivated by these challenges, we propose a novel algorithm inspired by Shapley value---a cooperative game-theoretic concept--- that is able to leverage the strong interdependencies in the effects of edge removals in the search space. We efficiently approximate Shapley values using a randomized algorithm with probabilistic guarantees. Our experiments, show that the proposed algorithm outperforms competing solutions in terms of k-core minimization while being able to handle large graphs. Moreover, we illustrate how KCM can be applied in the analysis of the k-core resilience of networks.
APA, Harvard, Vancouver, ISO, and other styles
7

Patel, Jay, and Matthew I. Campbell. "An Approach to Automate Concept Generation of Sheet Metal Parts Based on Manufacturing Operations." In ASME 2008 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2008. http://dx.doi.org/10.1115/detc2008-49648.

Full text
Abstract:
This paper describes an approach to automate the design for sheet metal parts that are not only novel and manufacturable but also satisfies multiple objective functions such as material cost and manufacturability. Unlike commercial software tools such as Pro/SHEETMETAL which aids the user in finalizing and determining the sequence of manufacturing operations for a specified component, our approach starts with spatial constraints in order to create the component geometries and helps the designer design. While there is an enormous set of parts that can feasibly be generated with sheet metal, it is difficult to define this space systematically. To solve this problem, we currently have 88 design rules that have been developed for four basic sheet metal operations: slitting, notching, shearing, and bending. A recipe of the operations for a final optimal design is then presented to the manufacturing engineers thus saving them time and cost. The technique revealed in this paper represents candidate solutions as a graph of nodes and arcs where each node is a rectangular patch of sheet metal, and modifications are progressively made to the sheet to maintain the parts manufacturability. They are presented in the form of Standard Tessellation Language files (.stl) that can be transferred into available modeling software for further analysis. The overall purpose of this research is to provide creative designs to the designer granting him/her a new perspective and to check all the solutions for manufacturability in the early stage of design process. An example sheet metal design problem is shown in this paper with some of the preliminary designs that our approach created.
APA, Harvard, Vancouver, ISO, and other styles
8

Zaharova, Alena, and Dmitriy Aleksandrovich Korostelev. "Visualizing Methods of Multi-criteria Alternatives for Pairwise Comparison Procedure." In International Conference "Computing for Physics and Technology - CPT2020". Bryansk State Technical University, 2020. http://dx.doi.org/10.30987/conferencearticle_5fce2770a0d219.60631258.

Full text
Abstract:
The article deals with the problem of choosing a preferred alternative in a pairwise comparison procedure. The difficulties of applying this procedure in a case of using alternatives with a large number of criteria are noted. It is proposed to supplement the procedure of expert pairwise comparison with visualization tools of multi-criteria alternatives. The paper considers several visualization methods for multi-criteria alternatives for pairwise comparison procedures: histograms, two-dimensional graphs, three-dimensional surfaces, probability distribution diagrams, visualization based on modifications of radar and radial diagrams, as well as combined methods. It described an experimental study of the application of the considered method for the task of determining the preferred alternative by the example of choosing one of two OpenFoam solvers (rhoCentralFoam and pisaCentralFoam), with the help of which estimates of the accuracy of calculating the inviscid flow around a cone were obtained. Each solver is characterized by 288 criteria. It is shown that the use of some of the methods considered does not make it possible for the expert to make a choice. In this case, a good result was obtained using methods for constructing three-dimensional surfaces, probability distribution diagrams, as well as using the combined method based on modified radar diagrams. It is concluded that the rhoCentralFoam solver is more preferable if there are no additional criteria for ranking the criteria. The possibility of using the combined method in combination with the ranking procedure of criteria (or their groups) during decision-making is also noted.
APA, Harvard, Vancouver, ISO, and other styles
9

Martin, Holger. "Reynolds, Maxwell, and the Radiometer, Revisited." In 2010 14th International Heat Transfer Conference. ASMEDC, 2010. http://dx.doi.org/10.1115/ihtc14-22023.

Full text
Abstract:
In 1969, S. G. Brush and C. W. F. Everitt published a historical review, that was reprinted as subchapter 5.5 Maxwell, Osborne Reynolds, and the radiometer, in Stephen G. Brush’s famous book The Kind of Motion We Call Heat. This review covers the history of the explanation of the forces acting on the vanes of Crookes radiometer up to the end of the 19th century. The forces moving the vanes in Crookes radiometer (which are not due to radiation pressure, as initially believed by Crookes and Maxwell) have been recognized as thermal effects of the remaining gas by Reynolds — from his experimental and theoretical work on Thermal Transpiration and Impulsion, in 1879 — and by the development of the differential equations describing Thermal Creeping Flow, induced by tangential stresses due to a temperature gradient on a solid surface by Maxwell, earlier in the same year, 1879. These fundamental physical laws have not yet made their way into the majority of textbooks of heat transfer and fluid mechanics so far. A literature research about the terms of Thermal Transpiration and Thermal Creeping Flow, in connection with the radiometer forces, resulted in a large number of interesting papers; not only the original ones as mentioned in subchapter 5.5 of Brush’s book, but many more in the earlier twentieth century, by Martin Knudsen, Wilhelm Westphal, Albert Einstein, Theodor Sexl, Paul Epstein and others. The forces as calculated from free molecular flow (by Knudsen), increase linearly with pressure, while the forces from Maxwell’s Thermal Creeping Flow decrease with pressure. In an intermediate range of pressures, depending on the characteristic geometrical dimensions of flow channels or radiometer vanes, an appropriate interpolation between these two kinds of forces, as suggested by Wilhelm Westphal and later by G. Hettner, goes through a maximum. Albert Einstein’s approximate solution of the problem happens to give the order of magnitude of the forces in the maximum range. A comprehensive formula and a graph of the these forces versus pressure combines all the relevant theories by Knudsen (1910), Einstein (1924), Maxwell (1879) (and Hettner (1926), Sexl (1928), and Epstein (1929) who found mathematical solutions for Maxwells creeping flow equations for non-isothermal spheres and circular discs, which are important for thermophoresis and for the radiometer). The mechanism of Thermal Creeping Flow will become of increasing interest in micro- and submicro-channels in various new applications, so it ought to be known to every graduate student of heat transfer in the future. That’s one of the reasons why some authors have recently questioned the validity of the classical Navier-Stokes, Fourier, and Fick equations: Dieter Straub (1996) published a book on an Alternative Mathematical Theory of Non-equilibrium Phenomena. Howard Brenner (since 2005) wrote a number of papers, like Navier-Stokes, revisited, and Bi-velocity hydrodynamics, explicitly pointing to the forces acting on the vanes of the lightmill, to thermophoresis and related phenomena. Franz Durst (since 2006) also developed modifications of the classical Navier-Stokes equations. So, Reynolds, Maxwell, and the radiometer may finally have initiated a revision of the fundamental equations of thermofluiddynamics and heat- and mass transfer.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Graph modification problem' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography