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

A survey of heuristics for matrix bandwidth reduction

COMPUTER SCIENCE REVIEW 2025年 56卷

作者： de Oliveira, S. L. Gonzaga Univ Fed Sao Paulo Inst Ciencia Tecnol Av Cesare Monsueto Giulio Lattes1201 Eugenio Melo BR-12247014 Sao Jose Dos Campos SP Brazil

This paper surveys heuristic methods for matrix bandwidth reduction, including low-cost methods and metaheuristics. This optimization min-max problem represents a demanding problem for heuristic methods. This paper poses the graph layout problem with its formal definition. The study also considers the application domains in which practitioners employ the linear graph layout problem on general matrices. Furthermore, this paper focuses on the techniques and procedures that provide excellent results and provides an extensive perspective of approaches to devise heuristics for matrix bandwidth reduction. Thus, this paper surveys most significant research in the field and examines the current state-of-the-art heuristics for the bandwidth reduction problem.

关键词： Sparse matrices Bandwidth reduction problem Heuristics graph algorithm Metaheuristics Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Injective coloring of subclasses of chordal graphs

引用

THEORETICAL COMPUTER SCIENCE 2025年 1023卷

作者： Panda, B. S. Ghosh, Rumki Indian Inst Technol Delhi Dept Math New Delhi 110016 India

An injective k-coloring of a graph G=(V,E) is a function f:V ->{1,2,& mldr;,k} such that for every pair of vertices u and v having a common neighbor, f(u)not equal f(v). The injective chromatic number chi(i)(G) of a graph G is the minimum k for which G admits an injective k-coloring. Given a graph G and a positive integer k, Decide Injective Coloring Problem is to decide whether G admits an injective k-coloring. Decide Injective Coloring Problem is known to be NP-complete for chordal graphs. In this paper, we strengthen this result by proving that Decide Injective coloring Problem remains NP-complete for undirected path graphs, a proper subclass of chordal graphs. Moreover, we show that it is not possible to approximate the injective chromatic number of an undirected path graph within a factor of n1/3-epsilon in polynomial time for every epsilon>0 unless ZPP = NP. On the positive side, we prove that the injective chromatic number of an interval graph is either Delta(G) or Delta(G)+1, where Delta(G) is the maximum degree of G. We also characterize the interval graphs having chi(i)(G)=Delta(G) and chi(i)(G)=Delta(G)+1. As a consequence of this characterization, we obtain a linear time algorithm to find the injective chromatic number of an interval graph.

关键词： Coloring Polynomial time algorithm NP-complete APX-complete graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP

引用

MATHEMATICAL PROGRAMMING 2025年第1期210卷 511-538页

作者： Jin, Billy Klein, Nathan Williamson, David P. Purdue Univ Daniels Sch Business W Lafayette IN 47907 USA Boston Univ Dept Comp Sci Boston MA USA Cornell Univ Sch Operat Res & Informat Engn Ithaca NY USA

A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP (sometimes called the Subtour LP or the Held-Karp bound) is at most 4/3 for symmetric instances of the TSP obeying the triangle inequality;that is, the cost of an optimal tour is at most 4/3 times the value of the value of the corresponding linear program. There is a variety of evidence in support of the conjecture (see, for instance, Goemans in Math Program 69:335-349, 1995;Benoit and Boyd in Math Oper Res 33:921-931, 2008). It has long been known that the integrality gap is at most 3/2 (Wolsey in Math Program Study 13:121-134, 1980;Shmoys and Williamson in Inf Process Lett 35:281-285, 1990). Despite significant efforts by the community, the conjecture remains open. In this paper we consider the half-integral case, in which a feasible solution to the LP has solution values in {0,1/2,1}. Such instances have been conjectured to be the most difficult instances for the overall four-thirds conjecture (Schalekamp et al. in Math Oper Res 39(2):403-417, 2014). Karlin et al. (in: Proceedings of the 52nd Annual ACM Symposium on the the Theory of Computing, ACM, New York, 2020), in a breakthrough result, were able to show that in the half-integral case, the integrality gap is at most 1.49993;Gupta et al. (in: Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, 2022. https://***/abs/2111.09290) showed a slight improvement of this result to 1.4983. Additionally, this result led to the first significant progress on the overall conjecture in decades;the same authors showed the integrality gap of the Subtour LP is at most 1.5-& varepsilon;for some & varepsilon;>10(-36) Karlin et al. in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). https://***/10.1109/FOCS54457.2022.00084. With the improvements on the 3/2 bound remaining very incremental, even in the half

关键词： Traveling salesman problem TSP Approximation algorithm Half integral graph algorithm Cycle cut Subtour LP Integrality gap

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for Minimizing the Kirchhoff Index via Adding Edges

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2025年第6期37卷 3342-3355页

作者： Zhou, Xiaotian Zehmakan, Ahad N. Zhang, Zhongzhi Fudan Univ Sch Comp Sci Shanghai Key Lab Intelligent Informat Proc Shanghai 200433 Peoples R China Australian Natl Univ Sch Comp Canberra ACT 2601 Australia Fudan Univ Res Inst Intelligent Complex Syst Shanghai 200433 Peoples R China

The Kirchhoff index, which is the sum of the resistance distance between every pair of nodes in a network, is a key metric for gauging network performance, where lower values signify enhanced performance. In this paper, we study the problem of minimizing the Kirchhoff index by adding edges. We first provide a greedy algorithm for solving this problem and give an analysis of its quality based on the bounds of the submodularity ratio and the curvature. Then, we introduce a gradient-based greedy algorithm as a new paradigm to solve this problem. To accelerate the computation cost, we leverage geometric properties, convex hull approximation, and approximation of the projected coordinate of each point. To further improve this algorithm, we use pre-pruning and fast update techniques, making it particularly suitable for large networks. Our proposed algorithms have nearly-linear time complexity. We provide extensive experiments on ten real networks to evaluate the quality of our algorithms. The results demonstrate that our proposed algorithms outperform the state-of-the-art methods in terms of efficiency and effectiveness. Moreover, our algorithms are scalable to large graphs with over 5 million nodes and 12 million edges.

关键词： Indexes Greedy algorithms Approximation algorithms Time complexity Vectors Resistance Optimization Data mining Laplace equations Error analysis Resistance distance Kirchhoff index graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Exponential speedup over locality in MPC with optimal memory

引用

DISTRIBUTED COMPUTING 2025年 1-38页

作者： Balliu, Alkida Brandt, Sebastian Fischer, Manuela Latypov, Rustam Maus, Yannic Olivetti, Dennis Uitto, Jara Gran Sasso Sci Inst Viale Francesco Crispi 7 I-67100 Laquila Italy CISPA Helmholtz Ctr Informat Secur Stuhlsatzenhaus 5 D-66123 Saarbrucken Germany Swiss Fed Inst Technol Dept Comp Sci Ramistr 101 CH-8092 Zurich Switzerland Aalto Univ Dept Comp Sci Otakaari 1 Espoo 02150 Uusimaa Finland Graz Univ Technol Fac Comp Sci & Biomed Engn Inffeldgasse 16B-2 A-8010 Graz Austria

Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and colorings. A successful line of research has been studying the complexities of LCLs on paths/cycles, trees, and general graphs, providing many interesting results for the LOCAL model of distributed computing. In this work, we initiate the study of LCL problems in the low-space Massively Parallel Computation (MPC) model. In particular, on forests, we provide a method that, given the complexity of an LCL problem in the LOCAL model, automatically provides an exponentially faster algorithm for the low-space MPC setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the results, we emphasize that all known (conditional) lower bounds for the MPC setting are obtained through lower bounds for LCL problems in the distributed setting in tree-like networks (either trees or high-girth graphs), and hence the LCL problems that we study are challenging already on trees. Moreover, our algorithms use optimal global memory, i.e., memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests this is not possible, hence using optimal memory requires new solutions.

关键词： Massively parallel computation Locally checkable labeling graph algorithm Forest

来源：评论

学校读者我要写书评

暂无评论

graph algorithmS ON A TREE-STRUCTURED PARALLEL COMPUTER

引用

BIT 1984年第3期24卷 333-340页

作者： YEH, DY LEE, DT CLEVELAND STATE UNIV DEPT COMP & INFORMAT SCICLEVELANDOH 44115 NORTHWESTERN UNIV DEPT ELECT ENGN & COMP SCIEVANSTONIL 60201

Parallel algorithms for some graph-theoretic problems on a tree-structured computer are presented. In particular, ifp denotes the number of processing elements, algorithms that run inO(n2/p) time for finding connected... 详细信息

关键词： SIMD computer systolic computer parallel algorithm graph algorithm time complexity

来源：评论

学校读者我要写书评

暂无评论

StLiter: A Novel algorithm to Iteratively Build the Compacted de Bruijn graph From Many Complete Genomes

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2022年第4期19卷 2471-2483页

作者： Yu, Changyong Mao, Keming Zhao, Yuhai Chang, Cheng Wang, Guoren Northeastern Univ Coll Comp Sci & Engn Shenyang 110819 Peoples R China Northeastern Univ Coll Software Shenyang 110819 Peoples R China Beijing Inst Life Natl Ctr Prot Sci Beijing Beijing Proteome Res Ctr State Key Lab Prote Beijing 102206 Peoples R China Beijing Inst Technol Sch Comp Sci & Technol Beijing 100081 Peoples R China

Recently, the compacted de Bruijn graph (cDBG) of complete genome sequences was successfully used in read mapping due to its ability to deal with the repetitions in genomes. However, current approaches are not flexible enough to fit frequently building the graphs with different k-mer lengths. Instead of building the graph directly, how can we build the compacted de Bruijin graph of longer k-mer based on the one of short k-mer? In this article, we present StLiter, a novel algorithm to build the compacted de Bruijn graph either directly from genome sequences or indirectly based on the graph of a short k-mer. For 100 simulated human genomes, StLiter can construct the graph of k-mer length 15-18 in 2.5-3.2 hours with maximal similar to 70GB memory in the case of without considering the reverese complements of the reference genomes. And it costs 4.5-5.9 hours when considering the reverse complements. In experiments, we compared StLiter with TwoPaCo, the state-of-art method for building the graph, on 4 datasets. For k-mer length 15-18, StLiter can build the graph 5-9 times faster than TwoPaCo using less maximal memory cost. For k-mer length larger than 18, given the graph of a short (k-x)-mer, such as x= 1-2, compared with TwoPaCo building the graph directly, StLiter can also build the graph more efficiently. The source codes of StLiter can be downloaded from web site https://***/BioLab-cz/StLiter.

关键词： graph algorithm indexing methods bioinformatics databases queries

来源：评论

学校读者我要写书评

暂无评论

CGTS: a site-clustering graph based tagSNP selection algorithm in genotype data

引用

BMC BIOINFORMATICS 2009年第Sup1期10卷 S71-S71页

作者： Wang, Jun Guo, Mao-zu Wang, Chun-yu Harbin Inst Technol Dept Comp Sci & Engn Harbin 150001 Peoples R China

Background: Recent studies have shown genetic variation is the basis of the genome-wide disease association research. However, due to the high cost on genotyping large number of single nucleotide polymorphisms (SNPs), it is essential to choose a small subset of informative SNPs (tagSNPs), which are able to capture most variation in a population, to represent the rest SNPs. Several methods have been proposed to find the minimum set of tagSNPs, but most of them still have some disadvantages such as information loss and block-partition limit. Results: This paper proposes a new hybrid method named CGTS which combines the ideas of the clustering and the graph algorithms to select tagSNPs on genotype data. This method aims to maximize the number of the discarding nontagSNPs in the given set. CGTS integrates the information of the LD association and the genotype diversity using the site graphs, discards redundant SNPs using the algorithm based on these graph structures. The clustering algorithm is used to reduce the running time of CGTS. The efficiency of the algorithm and quality of solutions are evaluated on biological data and the comparisons with three popular selecting methods are shown in the paper. Conclusion: Our theoretical analysis and experimental results show that our algorithm CGTS is not only more efficient than other methods but also can be get higher accuracy in tagSNP selection.

关键词： Linkage Disequilibrium graph algorithm Subgraph Density Diversity Subset Genotype Sequence

来源：评论

学校读者我要写书评

暂无评论

An algorithm for finding a maximum clique in a graph

引用

OPERATIONS RESEARCH LETTERS 1997年第5期21卷 211-217页

作者： Wood, DR Monash Univ Dept Comp Sci & Software Engn Clayton Vic 3168 Australia

This paper introduces a branch-and-bound algorithm for the maximum clique problem which applies existing clique finding and vertex coloring heuristics to determine lower and upper bounds for the size of a maximum clique. Computational results on a variety of graphs indicate the proposed procedure in most instances outperforms leading algorithms. (C) 1997 Elsevier Science B.V. All rights reserved.

关键词： graph algorithm maximum clique problem branch-and-bound algorithm vertex coloring fractional coloring

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for computing the intersection of all odd cycles in a graph

引用

DISCRETE APPLIED MATHEMATICS 1997年第1期73卷 27-34页

作者： Cai, LZ Schieber, B IBM CORP DIV RES TJ WATSON RES CTR YORKTOWN HTS NY 10598 USA CHINESE UNIV HONG KONG DEPT COMP SCI & ENGN SHATIN NT HONG KONG

We present a linear-time algorithm that finds all edges and vertices in the intersection of all odd cycles in a given graph. We also show an application of our algorithm to a variant of the satisfiability problem of B... 详细信息

关键词： graph algorithm odd cycle bipartite graph satisfiability problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：