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

11th international conference on algorithms and discrete applied mathematics, caldam 2025

ISBN: (纸本)9783031834370

the proceedings contain 30 papers. the special focus in this conference is on algorithms and discrete applied mathematics. the topics include: Parameterized Complexity of Coupon Coloring of Graphs;spectra of Eccentricity Matrices of Product of Graphs;almost Empty Monochromatic Polygons in Planar Point Sets;on the Parameterized Complexity of Odd Coloring;on Full-Separating Sets in Graphs;polynomial Time algorithms for Hop Domination;charging Station Placement for Limited Energy Robots;multipacking in the Euclidean Metric Space;partial Domination in Some Geometric Intersection Graphs;generalized Lettericity of Graphs;polynomial-Time algorithms for Path Cover on Trees and Graphs of Bounded Treewidth;Fast FPT algorithms for Grundy Number on Dense Graphs;on a Tight Bound for the Maximum Number of Vertices that Belong to Every Metric Basis;algorithms and Hardness Results for the (3, 1)-Cover Problem;extension Perfect Roman Domination;a Sub-quadratic Algorithm for the Minsum One Sink Location Problem on Balanced Binary Tree Networks;two Step Graph Protection Game;bipartite Domination in Graphs: Complexity and algorithms;packing Sets of Paths, Stars and Triangles: Tractability and Approximability;structural Parameterization of Minus Domination;an Algebraic Characterization of Strong Graphs;there are Finitely Many Uniformly Most Reliable Graphs of Corank 5;helly Number, Radon Number and Rank in Δ-Convexity on Graphs;forbidden Induced Subgraphs in Iterative Higher Order Line Graphs;total Domination and Open Packing in Two Subclasses of Triangle-Free Graphs;the MASEMPR Problem and Its Applications in Logistics;Broadcast Graph is NP-Complete;maximizing the Maximum Degree in Ordered Nearest Neighbor Graphs.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Parameterized Complexity of Coupon Coloring of Graphs 11th

Parameterized Complexity of Coupon Coloring of Graphs

引用

11th international conference on algorithms and discrete applied mathematics, caldam 2025

作者： Ashok, Pradeesha Devarakonda, Pradyun Phogat, Shiven Rayala, Swaroop A. Ram Sherin, J.A. International Institute of Information Technology Bangalore Bengaluru India PSG College of Technology Coimbatore India

ISBN: (纸本)9783031834370

Given a graph G(V, E), a q-coupon coloring of G refers to a coloring f:V→[q] such that the following is true for all v∈V: for all i∈[q], there exists u∈N(v) such that f(u)=i. Given a graph G, the q-Coupon Coloring problem is to decide whether G admits a q-coupon coloring. the q-Coupon Coloring problem is shown to be NP-complete. We initiate the study of parameterized complexity of the q-Coupon Coloring problem. It is implied by existing results that parameterization by q is unlikely to admit FPT algorithms. We study the q-Coupon Coloring problem parameterized by structural parameters including neighborhood diversity, twin cover, distance to clique and treewidth of the graph. We show FPT algorithms when the parameter is neighborhood diversity, twin cover and distance to clique and prove tight lower bounds when the parameter is treewidth. © the Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Broadcast Graph is NP-Complete 11th

Broadcast Graph is NP-Complete

引用

11th international conference on algorithms and discrete applied mathematics, caldam 2025

作者： Xu, Jinghan Li, Zhiyuan Guangdong Provincial Key Laboratory IRADS BNU-HKBU United International College Zhuhai519087 China

ISBN: (纸本)9783031834370

the broadcast model is widely used to describe the process of information dissemination from a single node to all nodes within an interconnected network. In this model, a graph represents the network, where vertices correspond to nodes and edges to communication links. the efficiency of this broadcasting process is evaluated by the broadcast time, the minimum discrete time units required to broadcast from a given vertex. Determining the broadcast time is referred to as the problem Broadcast Time. the set of vertices with the minimum broadcast time among the graph is called the broadcast center. Identifying this center or determining its size are both proven to be NP-hard. For a graph with n vertices, the minimum broadcast time is at least ⌈log2n⌉. the Broadcast Graph problem asks in a graph of n vertices, whether the broadcast time from any vertex equals ⌈log2n⌉. Extensive research over the past 50 years has focused on constructing broadcast graphs, which are optimal network topologies for one-to-all communication efficiency. However, the computational complexity of the Broadcast Graph problem has rarely been the subject of study. We believe that the difficulty lies in the mapping reduction for an NP-completeness proof. Consequently, we must construct broadcast graphs for yes-instances and non-broadcast graphs for no-instances. the most closely related result is the NP-completeness of Broadcast Time proved by Slater et al. in 1981. More recently, Fomin et al. has proved that Broadcast Time is fixed-parameter tractable. In this paper, we prove that Broadcast Graph is NP-complete by proving a reduction from Broadcast Time. We also improve the results on the complexity of the broadcast center problem. We show Broadcast Center Size is in Δp2, and is DP-hard, implying a complexity upper bound of Δp2-complete and a lower bound of DP-hard (NP ⊆DP⊆Δp2). © the Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： Information dissemination

来源：评论

学校读者我要写书评

暂无评论

algorithms and discrete applied mathematics 1

引用

丛书名： Lecture Notes in Computer Science

1000年

作者： Amitabha Bagchi Rahul Muthu

this book constitutes the proceedings of the 9th international conference on algorithms and discrete applied mathematics, caldam 2023, which was held in Gandhinagar, India, during February 9-11, 2023.

ISBN: (数字)9783031252112

ISBN: (纸本)9783031252105

关键词： mathematics of Computing Algorithm Analysis and Problem Complexity Computer Imaging, Vision, Pattern Recognition and Graphics Data Structures

来源：评论

学校读者我要写书评

暂无评论

algorithms for polyominoes based on the discrete Green theorem

引用

discrete applied mathematics 2005年第2-3期147卷 187-205页

作者： Brlek, S Labelle, G Lacasse, A Univ Quebec LaCIM Montreal PQ H3C 3P8 Canada

the use of Green's theorem and bivariate difference calculus provides a general and unifying framework for the description and generation of incremental algorithms. the method is applied in order to provide algorithms computing various statistics about polyominoes coded by 4-letter words describing their contour. these statistics include area, coordinates of the center of gravity, moment of inertia, size of projections, hook lengths, number of pixels in common with a given set of pixels, in particular the intersection of two polyominoes and also q-statistics for projections. (c) 2004 Elsevier B.V. All rights reserved.

关键词： discrete Green theorem algorithms statistics about polyominoes

来源：评论

学校读者我要写书评

暂无评论

algorithms and discrete applied mathematics 1

引用

丛书名： Lecture Notes in Computer Science

1000年

作者： Apurva Mudgal C. R. Subramanian

ISBN: (数字)9783030678999

ISBN: (纸本)9783030678982

this book constitutes the proceedings of the 7th international conference on algorithms and discrete applied mathematics, caldam 2021, which was held in Rupnagar, India, during February 11-13, 2021. the 39 papers presented in this volume were carefully reviewed and selected from 82 submissions. the papers were organized in topical sections named: approximation algorithms; parameterized algorithms; computational geometry; graph theory; combinatorics and algorithms; graph algorithms; and computational complexity.

关键词： mathematics of Computing Algorithm Analysis and Problem Complexity Data Structures and Information theory Computational mathematics and Numerical Analysis

来源：评论

学校读者我要写书评

暂无评论

algorithms for polyominoes based on the discrete Green theorem

Algorithms for polyominoes based on the discrete Green theor...

引用

11th international conference on discrete Geometry for Computer Imagery

作者： Brlek, S Labelle, G Lacasse, A Univ Quebec LaCIM Montreal PQ H3C 3P8 Canada

关键词： discrete Green theorem algorithms statistics about polyominoes

来源：评论

学校读者我要写书评

暂无评论

One-Sided discrete Terrain Guarding and Chordal Graphs 7th

One-Sided Discrete Terrain Guarding and Chordal Graphs

引用

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

作者： Prahlad Narasimhan, Kasthurirangan National Institute of Science Education and Research HBNI Bhubaneswar India

ISBN: (纸本)9783030678982

the Terrain Guarding problem, a variant of the famous Art Gallery problem, has garnered significant attention over the last two decades in Computational Geometry from the viewpoint of complexity and approximability. Both the continuous and discrete versions of the problem were shown to be NP-Hard in [14] and to admit a PTAS [8, 15]. the biggest unsolved question regarding this problem is if it is fixed-parameter tractable with respect to the size of the guard set. In this paper, we present two theorems that establish a relationship between a restricted case of the Annotated Terrain Guarding problem and the Clique Cover problem in chordal graphs. these theorems were proved in [11] for a special class of terrains called orthogonal terrains and were used to present a FPT algorithm with respect to the parameter that we require for discrete Orthogonal Terrain Guarding in [2]. We hope that the results obtained in this paper can, in future work, be used to produce such an algorithm for discrete Terrain Guarding. © 2021, Springer Nature Switzerland AG.

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

Socio-cognitively inspired ant colony optimization

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2017年 21卷 397-406页

作者： Byrski, Aleksander Swiderska, Ewelina Lasisz, Jakub Kisiel-Dorohinicki, Marek Lenaerts, Tom Samson, Dana Indurkhya, Bipin Nowe, Ann AGH Univ Sci & Technol Dept Comp Sci Fac Comp Sci Elect & Telecommun Al Mickiewicza 30 PL-30059 Krakow Poland Univ Libre Bruxelles ULB CP212 Campus PlaineBlvd Triomphe B-1050 Brussels Belgium Catholic Univ Louvain IPSY Pl Cardinal Mercier 10 Bte L3-05-01 A B-1348 Louvain La Neuve Belgium Jagiellonian Univ Inst Philosophy Ul Grodzka 52 PL-31044 Krakow Poland Vrije Univ Brussel Blvd Plaine 2 B-1050 Ixelles Belgium

Recently we proposed an application of ant colony optimization (ACO) to simulate socio-cognitive features of a population, incorporating perspective-taking ability to generate differently acting ant colonies. Although our main goal was simulation, we took advantage of the fact that the quality of the constructed system was evaluated based on selected traveling salesman problem instances, and the resulting computing system became a metaheuristic, which turned out to be a promising method for solving discrete problems. In this paper, we extend the initial sets of populations driven by different perspective-taking inspirations, seeking both optimal configuration for solving a number of TSP benchmarks, at the same time constituting a tool for analyzing socio-cognitive features of the individuals involved. the proposed algorithms are compared against classic ACO, and are found to prevail in most of the benchmark functions tested. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Ant-colony optimization discrete optimization Sodo-cognitive inspirations Metaheuristics Agent-based simulation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：