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

Injective coloring of some subclasses of bipartite graphs and chordal graphs

DISCRETE APPLIED MATHEMATICS 2021年 291卷 68-87页

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

A vertex coloring of a graph G = (V, E) that uses k colors is called an injective k-coloring of G if no two vertices having a common neighbor have the same color. The minimum k for which G has an injective k-coloring is called the injective chromatic number of G. Given a graph G and a positive integer k, the DECIDE INJECTIVE COLORING PROBLEM iS to decide whether G admits an injective k-coloring. It is known that DECIDE INJECTIVE COLORING PROBLEM is NP-complete for bipartite graphs. In this paper, we strengthen this result by showing that this problem remains NP-complete for perfect elimination bipartite graphs, star-convex bipartite graphs and comb-convex bipartite graphs, which are proper subclasses of bipartite graphs. Moreover, we show that for every epsilon > 0, it is not possible to efficiently approximate the injective chromatic number of a perfect elimination bipartite graph within a factor of n(1/3-epsilon) unless ZPP = NP. On the positive side, we propose a linear time algorithm for biconvex bipartite graphs and O(nm) time algorithm for convex bipartite graphs for finding the optimal injective coloring. We prove that the injective chromatic number of a chordal bipartite graph can be determined in polynomial time. It is known that DECIDE INJECTIVE COLORING PROBLEM is NP-complete for chordal graphs. We give a linear time algorithm for computing the injective chromatic number of proper interval graphs, which is a proper subclass of chordal graphs. DECIDE INJECTIVE COLORING PROBLEM is also known to be NP-complete for split graphs. We show that DECIDE INJECTIVE COLORING PROBLEM remains NP-complete for K-1,K-t-free split graphs for t >= 4 and polynomially solvable for t <= 3. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Injective coloring Polynomial time algorithm NP-complete Inapproximability graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Narrow sieves for parameterized paths and packings

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年 87卷 119-139页

作者： Bjorklund, Andreas Husfeldt, Thore Kaski, Petteri Koivisto, Mikko Lund Univ Dept Comp Sci POB 118 SE-22100 Lund Sweden IT Univ Copenhagen DK-2300 Copenhagen Denmark Aalto Univ Dept Informat & Comp Sci HIIT POB 15400 FI-00076 Aalto Finland Univ Helsinki HIIT Dept Comp Sci POB 68 FI-00014 Helsinki Finland

We present parameterized algorithms for the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space. The constant bases of the exponentials are significantly smaller than in previous works;for example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with d colors in time within a polynomial factor of 2((d-1)n/2). Our techniques generalize an algebraic approach studied in various recent works. (c) 2017 Elsevier Inc. All rights reserved.

关键词： Determinant Edge coloring graph algorithm k-Path Multidimensional matching Sieve Set packing Polynomial identity testing Randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

An Improved Sufficient Condition Tor Reconfiguration of List Edge-Colorings in a Tree

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2012年第3期E95D卷 737-745页

作者： Ito, Takehiro Kawamura, Kazuto Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

We study the problem of reconfiguring one list edge-coloring of a graph into another list edge-coloring by changing only one edge color assignment at a time, while at all times maintaining a list edge-coloring, given a list of allowed colors for each edge. Ito, Kaminski and Demaine gave a sufficient condition so that any list edge-coloring of a tree can be transformed into any other. In this paper, we give a new sufficient condition which improves the known one. Our sufficient condition is best possible in some sense. The proof is constructive, and yields a polynomial-time algorithm that finds a transformation between two given list edge-colorings of a tree with n vertices via O(n(2)) recoloring steps. We remark that the upper bound O(n(2)) on the number of recoloring steps is tight, because there is an infinite family of instances on paths that satisfy our sufficient condition and whose reconfiguration requires Omega(n(2)) recoloring steps.

关键词： graph algorithm list edge-coloring reachability on solution space reconfiguration problem tree

来源：评论

学校读者我要写书评

暂无评论

An ant colony hyperheuristic approach for matrix bandwidth reduction

引用

APPLIED SOFT COMPUTING 2020年 94卷 106434-106434页

作者： de Oliveira, S. L. Gonzaga Silva, L. M. Univ Fed Lavras Lavras Brazil

This paper considers the bandwidth reduction problem for large-scale matrices in serial computations. A heuristic for bandwidth reduction reorders the rows and columns of a given sparse matrix so that the method places entries with a nonzero value as close to the main diagonal as possible. Bandwidth optimization is a critical issue for many scientific and engineering applications. In this regard, this paper proposes an ant colony hyperheuristic approach for the bandwidth reduction of symmetric and nonsymmetric matrices. The ant colony hyperheuristic approach evolves and selects graph theory bandwidth reduction algorithms for application areas. This paper evaluates the resulting heuristics for bandwidth reduction in each application area against the most promising low-cost heuristics for bandwidth reduction. This paper also includes a numerical examination of the current state-of-the-art metaheuristic algorithms for matrix bandwidth reduction. The results yielded on a wide-ranging set of standard benchmark matrices showed that the proposed approach outperformed state-of-the-art low-cost heuristics for bandwidth reduction when applied to problem cases arising from several application areas, clearly indicating the promise of the proposal. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Bandwidth reduction Sparse matrix Ant colony optimization Hyperheuristic Reordering algorithms Renumbering Ordering graph labeling graph algorithm

来源：评论

学校读者我要写书评

暂无评论

On end-vertices of Lexicographic Breadth First Searches

引用

DISCRETE APPLIED MATHEMATICS 2010年第5期158卷 434-443页

作者： Corneil, Derek G. Koehler, Ekkehard Lanlignel, Jean-Marc Brandenburg Tech Univ Cottbus Math Inst D-03044 Cottbus Germany Univ Toronto Dept Comp Sci Toronto ON Canada Univ Montpellier 2 LIRMM F-34095 Montpellier 5 France

Recently Lexicographic Breadth First Search (LBFS) has received considerable attention and has often been employed in a multi-sweep fashion. One variant of LBFS called LBFS+ breaks ties by choosing the last vertex of the tied set in a previous LBFS. This has motivated the study of vertices that may appear last in an LBFS (called end-vertices). In this paper, we present various theoretical and algorithmic results concerning end-vertices. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Lexicographic breadth first search graph algorithm Complexity Simplicial vertex graph classes Chordal graphs Interval graphs AT-free graphs Cocomparability graphs

来源：评论

学校读者我要写书评

暂无评论

Minimal cutwidth linear arrangements of abelian Cayley graphs

引用

DISCRETE MATHEMATICS 2008年第20期308卷 4670-4695页

作者： Berend, Daniel Korach, Ephraim Lipets, Vladimir Ben Gurion Univ Negev Dept Math IL-84105 Beer Sheva Israel Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel Ben Gurion Univ Negev Dept Ind Engn & Management IL-84105 Beer Sheva Israel

We find the minimal cutwidth and bisection width values for abelian Cayley graphs with up to 4 generators and present an algorithm for finding the corresponding optimal ordering. We also find minimal cuts of each orde... 详细信息

关键词： combinatorial optimization graph algorithm Cayley graphs MINCUT linear arrangement

来源：评论

学校读者我要写书评

暂无评论

Reconfiguring spanning and induced subgraphs

引用

THEORETICAL COMPUTER SCIENCE 2020年 806卷 553-566页

作者： Hanaka, Tesshu Ito, Takehiro Mizuta, Haruka Moore, Benjamin Nishimura, Naomi Subramanya, Vijay Suzuki, Akira Vaidyanathan, Krishna Chuo Univ Fac Sci & Engn Bunkyo Ku 1-13-27 Kasuga Tokyo 1128551 Japan Tohoku Univ Grad Sch Informat Sci Aoba Ku 6-6-05 Aoba Sendai Miyagi 9808579 Japan Univ Waterloo Dept Combinator & Optimizat 200 Univ Ave West Waterloo ON N2L 3G1 Canada Univ Waterloo David R Cheriton Sch Comp Sci 200 Univ Ave West Waterloo ON N2L 3G1 Canada

SUBgraph RECONFIGURATION is a family of problems focusing on the reachability of the solution space in which feasible solutions are subgraphs, represented either as sets of vertices or sets of edges, satisfying a prescribed graph structure property. Although there has been previous work that can be categorized as SUBgraph RECONFIGURATION, most of the related results appear under the name of the property under consideration;for example, independent set, clique, and matching. In this paper, we systematically clarify the complexity status of SUBgraph RECONFIGURATION with respect to graph structure properties. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Combinatorial reconfiguration graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding the Maximum k-Balanced Biclique on Weighted Bipartite graphs

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2023年第8期35卷 7994-8007页

作者： Zhao, Yiwei Chen, Zi Chen, Chen Wang, Xiaoyang Lin, Xuemin Zhang, Wenjie East China Normal Univ Shanghai 200050 Peoples R China Univ Wollongong Wollongong NSW 2522 Australia Univ New South Wales Sydney NSW 2052 Australia Shanghai Jiao Tong Univ Shanghai 200240 Peoples R China

Bipartite graphs are widely used to capture the relationships between two types of entities. In bipartite graph analysis, finding the maximum balanced biclique (MBB) is an important problem with numerous applications. A biclique is balanced if its two disjoint vertex sets are of equal size. However, in real-world scenarios, each vertex is associated with a weight to denote its properties, such as influence, i.e., weighted bipartite graph. For weighted bipartite graphs, the previous studies for MBB are no longer applicable due to the ignorance of weight. To fill the gap, in this paper, we propose a reasonable definition of "balance" by restricting the weight difference between two sides of a biclique within k. Given a weighted bipartite graph G and a constraint k, we aim to find the maximum k-balanced biclique (Max k BB) with the maximum weight. To address the problem, we first propose an approach based on biclique enumeration on single side of G following the Branch-and-Bound framework. To improve the performance, we further devise three optimization strategies to prune invalid search branches. Moreover, we utilize graph reduction strategy to reduce the redundant search space. Extensive experiments are conducted on 12 real bipartite datasets to demonstrate the efficiency, effectiveness and scalability of our proposed algorithms. The experimental results show that our algorithms can address MBB detection problem efficiently, and the case study demonstrates the effectiveness of our model compared with MBB model.

关键词： Balanced biclique bipartite graph graph algorithm weighted vertex

来源：评论

学校读者我要写书评

暂无评论

A C-tree decomposition algorithm for 2D and 3D geometric constraint solving

引用

COMPUTER-AIDED DESIGN 2006年第1期38卷 1-13页

作者： Gao, XS Lin, Q Zhang, GF Acad Sinica AMSS Inst Syst Sci Key Lab Math Mechanizat Beijing 100080 Peoples R China Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China

In this paper, we propose a method which can be used to decompose a 2D or 3D constraint problem into a C-tree. With this decomposition, a geometric constraint problem can be reduced into basic merge patterns, which are the smallest problems we need to solve in order to solve the original problem in certain sense. Based on the C-tree decomposition algorithm, we implemented a software package MMP/Geometer. Experimental results show that MMP/Geometer finds the smallest decomposition for all the testing examples efficiently. (c) 2005 Elsevier Ltd. All rights reserved.

关键词： geometric constraint solving parametric CAD general construction sequence basic merge pattern decomposition tree graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast determination of structurally cohesive subgroups in large networks

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2016年第Part1期17卷 62-72页

作者： Sinkovits, Robert S. Moody, James Oztan, B. Tolga White, Douglas R. Univ Calif San Diego San Diego Supercomp Ctr San Diego CA 92103 USA Duke Univ Dept Sociol Durham NC 27706 USA King Abdulaziz Univ Jeddah Saudi Arabia Univ Calif Irvine Dept Anthropol Irvine CA USA Univ Calif Irvine Inst Math Behav Sci Irvine CA USA

Structurally cohesive subgroups are a powerful and mathematically rigorous way to characterize network robustness. Their strength lies in the ability to detect strong connections among vertices that not only have no neighbors in common, but that may be distantly separated in the graph. Unfortunately, identifying cohesive subgroups is a computationally intensive problem, which has limited empirical assessments of cohesion to relatively small graphs of at most a few thousand vertices. We describe here an approach that exploits the properties of cliques, k-cores and vertex separators to iteratively reduce the complexity of the graph to the point where standard algorithms can be used to complete the analysis. As a proof of principle, we apply our method to the cohesion analysis of a 29,462-vertex biconnected component extracted from a 128,151-vertex co-authorship data set. (C) 2016 Elsevier B.V. All rights reserved.

关键词： graph algorithm Social network Cohesive subgroup Vertex separator

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：