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

27th Annual European Symposium on algorithms (ESA)

作者： Rutter, Ignaz Strash, Darren Stumpf, Peter Vollmer, Michael Univ Passau Fac Comp Sci & Math Passau Germany Hamilton Coll Dept Comp Sci Clinton NY 13323 USA Karlsruhe Inst Technol KIT Dept Informat Karlsruhe Germany

ISBN: (纸本)9783959771245

In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study of simultaneous representations is the sunflower case where all objects share the same common structure. While the recognition problem for general simultaneous interval graphs - the simultaneous version of arguably one of the most well-studied graph classes - is NP-complete, the complexity of the sunflower case for three or more simultaneous interval graphs is currently open. In this work we settle this question for proper interval graphs. We give an algorithm to recognize simultaneous proper interval graphs in linear time in the sunflower case where we allow any number of simultaneous graphs. Simultaneous unit interval graphs are much more "rigid" and therefore have less freedom in their representation. We show they can be recognized in time O(vertical bar V vertical bar . vertical bar E vertical bar) for any number of simultaneous graphs in the sunflower case where G = (V, E) is the union of the simultaneous graphs. We further show that both recognition problems are in general NP-complete if the number of simultaneous graphs is not fixed. The restriction to the sunflower case is in this sense necessary.

关键词： Intersection Graphs recognition algorithm Proper/Unit Interval Graphs Simultaneous Representations

来源：评论

学校读者我要写书评

暂无评论

Unique square property and fundamental factorizations of graph bundles

Unique square property and fundamental factorizations of gra...

引用

4th Slovenian Graph Theory Conference

作者： Zmazek, B Zerovnik, J Univ Maribor Fac Mech Engn FS SLO-2000 Maribor Slovenia Univ Maribor Dept Math PEF SLO-2000 Maribor Slovenia Inst Math Phys & Mech Dept Theoret Comp Sci Ljubljana 1111 Slovenia

Graph bundles generalize the notion of covering graphs and graph products. In Imrich et al. (Discrete Math. 167/168 (1998) 393) authors constructed an algorithm that finds a presentation as a nontrivial cartesian graph bundle for all graphs that are cartesian graph bundles over triangle-free simple base using the relation delta(*) having the square property. An equivalence relation R on the edge set of a graph has the (unique) square property if and only if any pair of adjacent edges which belong to distinct R-equivalence classes span exactly one induced 4-cycle (with opposite edges in the same R-equivalence class). In this paper we define the unique square property and show that any weakly 2-convex equivalence relation possessing the unique square property determines the fundamental factorization of a graph as a nontrivial cartesian graph bundle over an arbitrary base graph, whenever it separates degenerate and nondegenerate edges of the factorization. (C) 2002 Elsevier Science B.V. All rights: reserved.

关键词： graph bundles Cartesian graph bundles recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Mit :: Ai :: Aim :: Aitr-1374

引用

2016年

[Auto Generated] 5.4.3 2D Alignment with Gaussian Error Measure . . . . . . 5.4.4 Linear Combination of Views . . . . . . . . . . . . . . 5.5 R esults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5.... 详细信息

[Auto Generated] 5.4.3 2D Alignment with Gaussian Error Measure . . . . . . 5.4.4 Linear Combination of Views . . . . . . . . . . . . . . 5.5 R esults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5.1 3D Alignm ent . . . . . . . . . . . . . . . . . . . . . . . 5.5.2 Number of Training Examples in the Absence of Noise 5.5.3 Number of Training Examples in the Presence of Noise 93 94 95 95 95 96 97 97 97 98 98 99 102 113 113 113 114 114 115 133 133 135 135 136 138 139 140 141 143

关键词： aitr-1374 algorithm based recognition bounded bounded error error error bounds error recognition features image linear combination model object object recognition objects rast algorithm recognition recognition algorithm transformation transformation space visual object

来源：评论

学校读者我要写书评

暂无评论

The bipartite travelling salesman problem: A pyramidally solvable case

引用

OPERATIONS RESEARCH LETTERS 2024年 55卷

作者： Deineko, Vladimir G. Klinz, Bettina Woeginger, Gerhard J. Univ Warwick Warwick Business Sch Coventry CV4 7AL England Graz Univ Technol Inst Discrete Math Graz Austria Rhein Westfal TH Aachen Dept Comp Sci Aachen Germany

Given k blue cities, k red cities and a 2k x 2k distance matrix, the task in the bipartite travelling salesman problem is to find a shortest tour which alternately visits blue and red cities. We consider the special case of Van der Veen distance matrices and show that it remains NP-hard in general but can be solved in O(k2) time when all vertices with odd indices are blue and all with even indices are red. (c) 2024 Published by Elsevier B.V.

关键词： Combinatorial optimisation Bipartite travelling salesman problem Pyramidally solvable case 63605ec6eb4e243dcb2eeb7d Van der Veen matrix recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

High-intensity lightning recognition system using Very Low Frequency signal features

引用

JOURNAL OF ATMOSPHERIC AND SOLAR-TERRESTRIAL PHYSICS 2021年 216卷 105520-105520页

作者： Arshad, N. S. Abdullah, M. Samad, S. A. Abdullah, N. Univ Kebangsaan Malaysia Fac Engn & Built Environm Dept Elect Elect & Syst Engn Bangi 43600 Selangor Malaysia Univ Malaysia Perlis Fac Elect Engn Technol Kampus Alam UniMAP Arau 02600 Perlis Malaysia Univ Kebangsaan Malaysia Inst Climate Change Space Sci Ctr ANGKASA Bangi 43600 Selangor Malaysia Kawasan Inst Penyelidikan TNB Res Sdn Bhd Lightning & Earthing Grp 1 Lorong Ayer Itam Kajang 43000 Selangor Malaysia

Commercial lightning detection networks offer detailed lightning stroke data upon subscription. Alternatively, the lightning monitoring system can be deployed at lower cost using Very Low Frequency (VLF) signal reception. With that, a dual-class high-intensity lightning recognition algorithm was developed using VLF signal features to identify the severity of lightning occurrence in the vicinity of 500 km from a single VLF signal path. The algorithm combined feature extraction, lightning detection, and lightning severity classification modules to identify two lightning severity classes based on the detected lightning peak current (by Lightning Detection System Network). For each lightning stroke sample, 20 VLF signal features (in terms of wavelet coefficient) in five signal parameters of four different levels of frequency bands were extracted as pattern representation prior to the classification. A combination of bagged and boosted trees ensemble classifiers achieved a lightning detection rate of 64.0% and correct lightning severity classification of 60.3%. These outstanding results exceeded lightning detection rate of between 20% and 40% in related past studies that applied the early VLF events technique. Good design practices such as cross-validation, feature selection, and ensemble classifiers contribute good generalisation and unbiased classification for small dataset.

关键词： VLF signal Lightning Feature extraction Feature classification recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Median filtering detection using LBP encoding pattern

引用

MULTIMEDIA TOOLS AND APPLICATIONS 2022年

作者： Wang, Xiaofeng Li, Xinai Tang, Chao Ding, Liangyiwen Xian Univ Technol Sch Sci Xian 710048 Shaanxi Peoples R China

In recent years, median filtering detection has a widely application in many fields such as images' processing history tracking, image editing detection, image anti-forensics analyzing and anti-steganalysis analyzing. In this paper, we propose two median filtering detection algorithms. The algorithm I is a recognition algorithm that can identify whether a given image has undergone median filtering. The algorithm II is a discriminating algorithm that can distinguish a median (average, Gaussian) filtered image from unfiltered images. Differing from the general framework of existing median filtering detectors, the contribution of our work is that the presented methods are not based on the statistical learning model. The proposed methods do not need any classifier, or any threshold. These methods are implemented by counting the number of specific Local Binary Pattern encoding patterns of a single image. Experimental results demonstrate that the proposed methods provide high accuracy and broad-spectrum robustness for tolerating content-preserving manipulations. Compared to state-of-the-art methods, the proposed methods exhibit high efficiency, high accuracy, and strong robustness.

关键词： Median filtering detection Local binary pattern Discriminating algorithm recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Recognizing Series-Parallel Matrices in Linear Time

引用

INFORMS JOURNAL ON COMPUTING 2023年第6期35卷 1404-1418页

作者： Walter, Matthias Univ Twente Dept Appl Math NL-7522 NB Enschede Netherlands

A series-parallel matrix is a binary matrix that can be obtained from an empty matrix by successively adjoining rows or columns that are copies of an existing row/column or have at most one one-entry. Equivalently, series-parallel matrices are representation matrices of graphic matroids of series-parallel graphs, which can be recognized in linear time. We propose an algorithm that, for an m-by-n matrix A with k nonzeros, determines in expected time whether A is series-parallel or returns a minimal non-seriesparallel submatrix of A. We complement the developed algorithm by an efficient O(m + n + k)implementation and report about computational results.

关键词： series-parallel recognition algorithm matroids

来源：评论

学校读者我要写书评

暂无评论

Generalized Fitch Graphs III: Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2021年第1期23卷 1页

作者： Hellmuth, Marc Seemann, Carsten R. Stadler, Peter F. Stockholm Univ Dept Math Stockholm Sweden Max Planck Inst Math Sci Leipzig Germany Univ Leipzig Bioinformat Grp Leipzig Germany Univ Vienna Inst Theoret Chem Vienna Austria Univ Nacl Colombia Fac Ciencias Bogota Colombia Santa Fe Inst Santa Fe NM 87501 USA

Binary relations derived from labeled rooted trees play an import role in mathematical biology as formal models of evolutionary relationships. The (symmetrized) Fitch relation formalizes xenology as the pairs of genes separated by at least one horizontal transfer event. As a natural generalization, we consider symmetrized Fitch maps, that is, symmetric maps epsilon that assign a subset of colors to each pair of vertices in X and that can be explained by a tree T with edges that are labeled with subsets of colors in the sense that the color m appears in epsilon(x, y) if and only if m appears in a label along the unique path between x and y in T. We first give an alternative characterization of the monochromatic case and then give a characterization of symmetrized Fitch maps in terms of compatibility of a certain set of quartets. We show that recognition of symmetrized Fitch maps is NP-complete. In the restricted case where vertical bar epsilon(x, y)vertical bar <= 1 the problem becomes polynomial, since such maps coincide with class of monochromatic Fitch maps whose graph-representations form precisely the class of complete multi-partite graphs.

关键词： Labeled Trees Fitch Relations Symmetrized Maps Splits and Quartets recognition algorithm NP-completeness Phylogenetics

来源：评论

学校读者我要写书评

暂无评论

Characterization of balanced graphs within claw-free graphs

引用

Procedia Computer Science 2023年 223卷 258-266页

作者： Lucía Busolini Guillermo Durán Martín D. Safe Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires (UBA) Buenos Aires Argentina Instituto de Cálculo UBA-CONICET Buenos Aires Argentina Departamento de Matemática Universidad Nacional del Sur (UNS) Bahía Blanca Argentina INMABB UNS-CONICET Bahía Blanca Argentina

A graph is balanced when its clique matrix is balanced. Bonomo, Durán, Lin and Szwarcfiter (2006) proved that a graph is balanced if and only if it contains no induced subgraphs known as extended odd suns. However, a characterization of balanced graphs by minimal forbidden induced subgraphs is not known. In this work, we find such a characterization when restricted to the class of claw-free graphs. As a consequence, we prove that there is an O(m 2 + n)-time algorithm that, given any graph, either decides that it is balanced or gives a certificate of the fact that it is not claw-free balanced.

关键词： balanced graphs claw-free graphs forbidden subgraphs recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Comparability digraphs: An analogue of comparability graphs

引用

DISCRETE MATHEMATICS 2024年第3期347卷

作者： Gao, Xiao-Lu Huang, Jing Xu, Shou-Jun Jiangsu Univ Sch Math Sci Zhenjiang 212013 Jiangsu Peoples R China Univ Victoria Dept Math & Stat Victoria BC V8W 2Y2 Canada Lanzhou Univ Sch Math & Stat Lanzhou 730000 Gansu Peoples R China

Comparability graphs are a popular class of graphs. We introduce as the digraph analogue of comparability graphs the class of comparability digraphs. We show that many concepts such as implication classes and the knotting graph for a comparability graph can be naturally extended to a comparability digraph. We give a characterization of comparability digraphs in terms of their knotting graphs. Semicomplete comparability digraphs contain in a sense all comparability graphs. One instrumental technique for analyzing the structure of comparability graphs is the Triangle Lemma for graphs (cf. Golumbic (1980) [7]). Using Triangle Lemma, Golumbic proved that a graph is a comparability graph if and only if no implication class of the graph is equal to its inverse. We give examples to show that a similar statement does not hold for general digraphs. We prove that it holds for semicomplete digraphs, that is, a semicomplete digraph is a comparability digraph if and only if no implication class of the digraph is equal to its inverse. The proof is done by generalizing the Triangle Lemma for graphs to semicomplete digraphs. This yields an O(n3)-time recognition algorithm for semicomplete comparability digraphs where n is the number of vertices of the input digraph. The correctness of the algorithm also implies several other characterizations for semicomplete comparability digraphs, akin to those for comparability graphs. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Comparability digraph Implication class Knotting graph Triangle Lemma Characterization recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：