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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

DAG-Pathwidth: graph algorithmic Analyses of DAG-Type Blockchain Networks

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2023年第3期E106D卷 272-283页

作者： Kasahara, Shoji Kawahara, Jun Minato, Shin-ichi Mori, Jumpei Nara Inst Sci & Technol Ikoma 6300192 Japan Kyoto Univ Kyoto 6068501 Japan

This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the view-point of graph algorithm theory. To use a DAG-type blockchain, NP-hard graph optimization problems on the DAG are required to be solved. Although various problems for undirected and directed graphs can be efficiently solved by using the notions of graph parameters, these currently known parameters are meaningless for DAGs, which implies that it is hopeless to design efficient algorithms based on the parameters for such problems. In this work, we propose a novel graph parameter for directed graphs called a DAG-pathwidth, which represents the closeness to a directed path. This is an extension of the pathwidth, a well-known graph parameter for undirected graphs. We analyze the features of the DAG-pathwidth and prove that computing the DAG-pathwidth of a DAG (directed graph in general) is NP-complete. Finally, we propose an efficient algorithm for a variant of the maximum k-independent set problem for the DAG-type blockchain when the DAG-pathwidth of the input graph is small.

关键词： graph algorithm computational complexity directed acyclic graph pathwidth blockchain

来源：评论

学校读者我要写书评

暂无评论

An O(k^2n^2) algorithm to Find a k-Partition in a k-Connected graph

引用

Journal of Computer Science & Technology 1994年第1期9卷 86-91页

作者：马军马绍汉 DepartmentofComputerScience ShandongUniversityJinan250100 DepartmentofComputerScience ShandongUniver

Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively, there is no general algorithm of finding a k-partition for a k-connected graph G = (V, E), where k is the vertex connectivity of G. In this paper, an O(k2n2) general algorithm of finding a k-partition for a k-connected graph is proposed, where n = |V|.

关键词： graph algorithm graph vertex connectivity k-partition of a graph

来源：评论

学校读者我要写书评

暂无评论

PARALLEL MATRIX AND graph algorithmS

引用

SIAM JOURNAL ON COMPUTING 1981年第4期10卷 657-675页

作者： DEKEL, E NASSIMI, D SAHNI, S NORTHWESTERN UNIV DEPT ELECT ENGN & COMP SCIEVANSTONIL 60201

Matrix multiplication algorithms for cube connected and perfect shuffle computers are presented. It is shown that in both these models two n×nn×nn \times n matrices can be multiplied in <span class="... 详细信息

Matrix multiplication algorithms for cube connected and perfect shuffle computers are presented. It is shown that in both these models two

n \times n

$n \times n$ matrices can be multiplied in

O (n

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：