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

6th international conference on algorithms and discrete applied mathematics, caldam 2020

ISBN: (纸本)9783030392185

the proceedings contain 38 papers. the special focus in this conference is on algorithms and discrete applied mathematics. the topics include: Determining Number of Generalized and Double Generalized Petersen Graph;self-centeredness of Generalized Petersen Graphs;weak Roman Bondage Number of a Graph;on the Geodetic and Hull Numbers of Shadow Graphs;indicated Coloring of Complete Expansion and Lexicographic Product of Graphs;smallest C2l+1-Critical Graphs of Odd-Girth 2k+1;ramsey Numbers for Line Graphs;Δ-Convexity Number and Δ-Number of Graphs and Graph Products;on Cartesian Products of Signed Graphs;partitioning Cographs into Two Forests and One Independent Set;list Distinguishing Number of pth Power of Hypercube and Cartesian Powers of a Graph;on Algebraic Expressions of Two-Terminal Directed Acyclic Graphs;the Relative Oriented Clique Number of Triangle-Free Planar Graphs Is 10;on the Minimum Satisfiability Problem;waiting for Trains: Complexity Results;oriented Diameter of Star Graphs;gathering over Meeting Nodes in Infinite Grid;0-1 Timed Matching in Bipartite Temporal Graphs;arbitrary Pattern Formation by Opaque Fat Robots with Lights;greedy Universal Cycle Constructions for Weak Orders;monitoring the Edges of a Graph Using Distances;a New Model in Firefighting theory;an Algorithm for Strong Stability in the Student-Project Allocation Problem with Ties;overlaying a Hypergraph with a Graph with Bounded Maximum Degree;parameterized algorithms for Directed Modular Width;on the Parameterized Complexity of Spanning Trees with Small Vertex Covers;minimum Conflict Free Colouring Parameterized by Treewidth;planar Projections of Graphs;new algorithms and Bounds for Halving Pseudolines;algorithms for Radon Partitions with Tolerance.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Growth Rate of the Number of Empty Triangles in the Plane 10th

Growth Rate of the Number of Empty Triangles in the Plane

引用

10th international conference on algorithms and discrete applied mathematics (caldam)

作者： Bhattacharya, Bhaswar B. Das, Sandip Islam, Sk. Samim Sen, Saumya Univ Penn Philadelphia PA USA Indian Stat Inst Kolkata India

ISBN: (纸本)9783031522123;9783031522130

Given a set P of n points in the plane, in general position, denote by N-Delta(P) the number of empty triangles with vertices in P. In this paper we investigate by how much N-Delta(P) changes if a point x is removed from P. By constructing a graph G(P)(x) based on the arrangement of the empty triangles incident on x, we transform this geometric problem to the problem of counting triangles in the graph G(P)(x). We study properties of the graph G(P)(x) and, in particular, show that it is kite-free. this relates the growth rate of the number of empty triangles to the famous Ruzsa-Szemeredi problem.

关键词： discrete geometry Empty triangles Kite-free graph

来源：评论

学校读者我要写书评

暂无评论

5-List Coloring Toroidal 6-Regular Triangulations in Linear Time 9th

5-List Coloring Toroidal 6-Regular Triangulations in Linear ...

引用

9th international conference on algorithms and discrete applied mathematics (caldam)

作者： Balachandran, Niranjan Sankarnarayanan, Brahadeesh Indian Inst Technol Dept Math Mumbai 400076 Maharashtra India

We give an explicit procedure for 5-list coloring a large class of toroidal 6-regular triangulations in linear time. We also show that these graphs are not 3-choosable.

ISBN: (纸本)9783031252105;9783031252112

We give an explicit procedure for 5-list coloring a large class of toroidal 6-regular triangulations in linear time. We also show that these graphs are not 3-choosable.

关键词： List coloring Toroidal graph Triangulation Regular graph Linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

A N-Dimensional discrete Chaotic Map and Its Performance 6

A N-Dimensional Discrete Chaotic Map and Its Performance

引用

6th international conference on Natural Language Processing (ICNLP)

作者： Gao, Xin Cai, Xiumei Wu, Chengmao Xian Univ Post & Telecommun Sch Automat Xian 710121 Peoples R China Xian Univ Post & Telecommun Sch Elect Engn Xian 710121 Peoples R China

ISBN: (纸本)9798350349122;9798350349115

In order to solve the problems of small key space and simple chaotic behavior of low-dimensional chaotic systems in discrete domain, an N-dimensional discrete chaotic mapping system is proposed. An N-dimensional discrete chaotic system is obtained by coupling Chebyshev mapping with ICMIC mapping. Taking two-dimensional chaotic mapping as an example, the Lyapunov index, bifurcation graph, correlation and other properties of the discrete chaotic system are analyzed and applied to more classical image encryption algorithms. Experimental simulation results show that the N-dimensional discrete chaotic mapping system has larger key space, better chaotic behavior, and better security performance for image encryption algorithms.

关键词： combined chaos Chebyshev map key space Lyapunov exponent

来源：评论

学校读者我要写书评

暂无评论

A New Model in Firefighting theory 6th

A New Model in Firefighting Theory

引用

6th international conference on algorithms and discrete applied mathematics

作者： Klein, Rolf Kubelb, David Langetepe, Elmar Sack, Joerg-Ruediger Schwarzwald, Barbara Univ Bonn Dept Comp Sci D-53115 Bonn Germany Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

ISBN: (纸本)9783030392185;9783030392192

Continuous and discrete models [1,5] for firefighting problems are well-studied in theoretical Computer Science. We introduce a new, discrete, and more general framework based on a hexagonal cell graph to study firefighting problems in varied terrains. We present three different firefighting problems in the context of this model;for two of which, we provide efficient polynomial time algorithms and for the third, we show NP-completeness. We also discuss possible extensions of the model and their implications on the computational complexity.

关键词： Cellular automaton Combinatorial algorithms Computational complexity discrete geometry Fire spread models Fire behaviour modeling Firefighting Forest fire simulation Frontal propagation Graph algorithms Graph theory NP-completeness Undecidability

来源：评论

学校读者我要写书评

暂无评论

Experimental Evaluation of a Local Search Approximation Algorithm for the Multiway Cut Problem 7th

Experimental Evaluation of a Local Search Approximation Algo...

引用

7th international conference on algorithms and discrete applied mathematics, caldam 2021

作者： Bloch-Hansen, Andrew Samei, Nasim Solis-Oba, Roberto Department of Computer Science The University of Western Ontario LondonONN6A 5B7 Canada IST Austria Am Campus 1 Klosterneuburg3400 Austria

ISBN: (纸本)9783030678982

In the multiway cut problem we are given a weighted undirected graph G= (V, E) and a set T⊆ V of k terminals. the goal is to find a minimum weight set of edges E′⊆ E with the property that by removing E′ from G all the terminals become disconnected. In this paper we present a simple local search approximation algorithm for the multiway cut problem with approximation ratio 2-2k. We present an experimental evaluation of the performance of our local search algorithm and show that it greatly outperforms the isolation heuristic of Dalhaus et al. and it has similar performance as the much more complex algorithms of Calinescu et al., Sharma and Vondrak, and Buchbinder et al. which have the currently best known approximation ratios for this problem. © 2021, Springer Nature Switzerland AG.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

the complexity of AND-decomposition of Boolean functions

引用

discrete applied mathematics 2020年 280卷 113-132页

作者： Emelyanov, Pavel Ponomaryov, Denis Ershov Inst Informat Syst Lavrentiev Av 6 Novosibirsk 630090 Russia Novosibirsk State Univ Pirogova St 1 Novosibirsk 630090 Russia

We consider the complexity of decomposing a Boolean function into a conjunction of components, which may share a (possibly empty) given set of variables.. Boolean functions are given as expressions in CNF, DNF, full DNF, and ANF and it is assumed that decomposition components must be in the same normal form as the input expression. We show that deciding decomposability is in general intractable for CNF and DNF already for the empty set of shared variables between the components. On the other hand, we demonstrate that for positive CNF and DNF and full DNF, the finest decomposition components wrt a given. can be computed in polynomial time (in the size of the input expression given as a string). the tractability results employ an efficient transformation of input expressions into series of expressions in ANFs aka Boolean polynomials, for which we provide a polynomial time factorization algorithm. Since the reduction leads to solving series of factorization tasks for Boolean polynomials, we discuss a number of ideas on how to optimize massive factorization and report preliminary experimental results. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Conjunctive decomposition Disjoint decomposition Polynomial factorization Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Waiting for Trains: Complexity Results 6th

Waiting for Trains: Complexity Results

引用

6th international conference on algorithms and discrete applied mathematics

作者： Tauer, Bjoern Fischer, Dennis Fuchs, Janosch Koch, Laura Vargas Zieger, Stephan Rhein Westfal TH Aachen Dept Comp Sci Aachen Germany Rhein Westfal TH Aachen Dept Econ & Business Aachen Germany Rhein Westfal TH Aachen Inst Transport Sci Aachen Germany

ISBN: (纸本)9783030392185;9783030392192

We introduce a model for train routing on railway systems. Trains route through a network over time from a start to an end depot. they occupy consecutive nodes and edges corresponding to their length and block each other. We study the case where the depots are part of the network (internal) and the case where the depots are not part of the network (external). the problem is a generalization of packet routing without buffers. We consider two different kinds of optimization problems. In the first, trains are only allowed to wait on predefined paths and in the second, trains are additionally allowed to shunt, i.e., change direction. In both cases, we are interested in minimizing the overall makespan. For waiting instances, we find NP-hardness results even on unidirectional paths. We also show W[1]-hardness and lower bounds on the running time using the Exponential Time Hypothesis. For shunting instances, we show PSPACE-completeness results on honeycomb graphs and transfer the previously shown NP-hardness results. We present a polynomial time algorithm for a special subclass of unidirectional paths.

关键词： Train scheduling Wormhole routing Packet routing Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Grey Wolf Optimization algorithm with discrete Hopfield Neural Network for 3 Satisfiability analysis 6

Grey Wolf Optimization algorithm with Discrete Hopfield Neur...

引用

6th international conference on mathematics: Pure, applied and Computation, ICOMPAC 2020

作者： Mansor, Mohd. Asyraf Kasihmuddin, Mohd Shareduwan Mohd Sathasivam, Saratha School of Distance Education Universiti Sains Malaysia Penang11800 USM Malaysia School of Mathematical Sciences Universiti Sains Malaysia Penang11800 USM Malaysia

An optimal learning algorithm contributes to the quality of the neuron states in the form of 3 Satisfiability logical representation during the retrieval phase of the discrete Hopfield Neural Network. Based on that basis, we proposed a modified bipolar Grey Wolf Optimization algorithm with a discrete Hopfield Neural Network for Boolean 3 Satisfiability analysis by manipulating the different levels of complexities. this work concerns the improvement in the learning phase which requires a robust iterative metaheuristic algorithm in minimizing the cost function of 3 Satisfiability logical representation with less iteration. Under some reasonable conditions, the proposed hybrid network will be assessed by employing several performance measures, in terms of learning errors, minimum energy evaluations, variability, and similarity analysis. To verify the compatibility of the Grey Wolf Optimization algorithm as a learning paradigm, the comparison was made with the hybrid model with an Exhaustive search. thus, the results proved the capability of the proposed learning algorithm in optimizing the learning and generating global minimum solutions for 3 Satisfiability logic based on the analysis obtained via various performance metrics evaluation. © Published under licence by IOP Publishing Ltd.

关键词： Learning algorithms

来源：评论

学校读者我要写书评

暂无评论

Mathematical Modelling of a Ranking Algorithm: the Case of the Social Network VKontakte

Mathematical Modelling of a Ranking Algorithm: The Case of t...

引用

international conference on Control Systems, Mathematical Modelling, Automation and Energy Efficiency (SUMMA)

作者： Ivan V. Kozitsin Denis A. Aivazov Laboratory of Active Systems Institute of Control Sciences of RAS Moscow Russia Discrete Mathematics Department Moscow Institute of Physics and Technology Dolgoprudny Russian Federation

ISBN: (数字)9798331532178

ISBN: (纸本)9798331532185

Ranking systems play a crucial role in shaping the online information landscape. these black-box algorithms utilize observable information on users' preferences and passions and recommend new friends/followees to users, sort out contents in users' news feeds, or even hint users what political opinions they have at the moment. Despite their importance in understanding the dynamics of social processes in the online domain, we still know very little about their organization. this paper attempts to fill this gap in the scientific knowledge and identifies a very specific ranking algorithm - the algorithm that sorts out comments under posts on social network VKontakte, a Russian popular online media platform. To this end, we located the set of $N=1000$ posts dedicated to the coronavirus pandemic topic between 12 December 2020 and 1 March 2021, and then downloaded comments attached to them. Besides this, for $n=50$ of these posts, we manually retrieved the order in which the comments appear in users' news feeds subject to the ranking algorithm being in charge. Using these data, we study the structure of the information cascades formed by these comments and organization of the ranking algorithm, trying to model it as a specific relevance function that is linear to the comment popularity metrics - the numbers of likes and replies. To identify the ranking algorithm, we developed a simple model of ranking, according to which comments with higher values of a relevance score should feature a higher priority in the news feed, with the score being a linear function of the popularity metrics. We calibrated this model on a dataset of labeled comments and found that both the popularity factors play a significant role in ranking, but the size of the branch has a slightly greater effect.

关键词： Measurement Analytical models Social networking (online) Pandemics Heuristic algorithms Organizations Search engines Mathematical models Feeds Object recognition

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：