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

DISCRETE APPLIED MATHEMATICS 2008年第13期156卷 2517-2529页

作者： Lozin, Vadim V. Milanic, Martin Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Univ Bielefeld Fac Technol AG Genome Informat D-4800 Bielefeld Germany

Method of augmenting graphs is a general approach to solve the maximum independent set problem. As the problem is generally NP-hard, no polynomial time algorithms are available to implement the method. However, when restricted to particular classes of graphs, tile approach may lead to efficient solutions. A famous example of this type is the maximum matching algorithm: it finds a maximum matching in a graph G, which is equivalent to finding a maximum independent set in the line graph of G. In the particular case of line graphs, the method reduces to finding augmenting (alternating) chains. Recent investigations of more general classes of graphs revealed many more types of augmenting graphs. In the present paper we study the problem of finding augmenting graphs different from chains. To simplify this problem, we introduce tile notion of a redundant set. This allows us to reduce the problem to finding some basic augmenting graphs. As a result, we obtain a polynomial time solution to the maximum independent set problem in a class of graphs which extends several previously studied classes including the line graphs. (c) 2008 Elsevier B.V. All rights reserved.

关键词： independent set augmenting graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Branch less, cut more and minimize the number of late equal-length jobs on identical machines

引用

THEORETICAL COMPUTER SCIENCE 2012年 465卷 49-60页

作者： Vakhania, Nodari UAEMor Fac Ciencias Cuernavaca Morelos Mexico

A simple greedy-type solution for a discrete optimization problem does not guarantee the optimality if the problem is sufficiently complicated. Dynamic programming is then a commonly used method, and a direct combinatorial algorithm is its reasonable alternative. Here we propose such an algorithm with some specific features, called branch less and cut more, abbreviated blesscmore. A blesscmore algorithm, like a branch-and-bound algorithm uses a solution tree whereas the branching and cutting criteria are based on the analysis of the so-called behavior alternatives. Our O(n(3) log n) blesscmore algorithm solves an earlier open problem of scheduling n equal-length jobs with release times and due-dates on a group of identical machines to minimize the number of late jobs. (c) 2012 Elsevier B.V. All rights reserved.

关键词： polynomial-time algorithm Solution tree Scheduling identical machines

来源：评论

学校读者我要写书评

暂无评论

Complexity and approximability of Minimum Path-Collection Exact Covers

引用

THEORETICAL COMPUTER SCIENCE 2023年 942卷 21-32页

作者： Ravelo, Santiago Valdes Fernandes, Cristina G. Univ Fed Rio Grande do Sul Inst Informat Porto Alegre Brazil Univ Sao Paulo Dept Comp Sci Sao Paulo Brazil

This work considers the Minimum Path-Collection Exact Cover (PCEC) and the Minimum k-Path Splitting Exact Cover (x-PSEC). Both problems receive a digraph G and a set P of paths in G, and their objective is to find a minimum cardinality set S of paths, whose elements are arc-disjoint and cover all arcs of G. Despite the similarities, the solutions for each problem must satisfy different properties. For x-PSEC, the set S must be obtained by splitting the paths in P in order to guarantee that no element of S has length greater than a given integer k. For PCEC, the paths in P cannot be split, and the elements of S are single arcs of G or complete paths of P. PCEC and x-PSEC have practical applications in network design and network monitoring systems, being also natural versions of graph covering problems. However, there are no theoretical studies on their complexity. This work not only presents NP-hardness results for the problems, but also proves that, unless P = NP, PCEC cannot be |P|O(1)-approximated in polynomial-time. Moreover, polynomial-time algorithms are presented for paths, cycles, and trees, and polynomial-time approximation algorithms are proposed for special cases of x-PSEC. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Exact edge cover Computational complexity Approximability polynomial-time algorithm Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

On the complexity of the vector connectivity problem

引用

THEORETICAL COMPUTER SCIENCE 2015年 591卷 60-71页

作者： Cicalese, Ferdinando Milanic, Martin Rizzi, Romeo Univ Verona Dept Comp Sci I-37100 Verona Italy Univ Primorska UP IAM SI-6000 Koper Slovenia Univ Primorska UP FAMNIT SI-6000 Koper Slovenia

We study a relaxation of the VECTOR DOMINATION problem called VECTOR CONNECTIVITY (VECCON). Given a graph G with a requirement r(v) for each vertex v, VECCON asks for a minimum cardinality set S of vertices such that every vertex v is an element of V \ S is connected to S via r(v) disjoint paths. In the paper introducing the problem, Boras et al. [4] gave polynomial-time solutions for VEcCoN in trees, cographs, and split graphs, and showed that the problem can be approximated in polynomial time on n-vertex graphs to within a factor of logn + 2, leaving open the question of whether the problem is NP-hard on general graphs. We show that VECCON is APX-hard in general graphs, and NP-hard in planar bipartite graphs and in planar line graphs. We also generalize the polynomial result for trees by solving the problem for block graphs. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Vector connectivity APX-hardness NP-hardness polynomial-time algorithm Block graphs

来源：评论

学校读者我要写书评

暂无评论

On the computational complexity of reconstructing lattice sets from their X-rays

引用

DISCRETE MATHEMATICS 1999年第1-3期202卷 45-71页

作者： Gardner, RJ Gritzmann, P Prangenberg, D Western Washington Univ Dept Math Bellingham WA 98225 USA Univ Technol Ctr Math Sci D-80290 Munich Germany Univ Trier D-54286 Trier Germany

We study the computational complexity of various inverse problems in discrete tomography. These questions are motivated by demands from the material sciences for the reconstruction of crystalline structures from images produced by quantitative high resolution transmission electron microscopy. We completely settle the complexity status of the basic problems of existence (data consistency), uniqueness (determination), and reconstruction of finite subsets of the d-dimensional integer lattice Z(d) that are only accessible via their line sums (discrete X-rays) in some prescribed finite set of lattice directions. Roughly speaking, it turns out that for all d greater than or equal to 2 and for a prescribed but arbitrary set of m greater than or equal to 2 pairwise nonparallel lattice directions, the problems are solvable in polynomial time if m=2 and are NP-complete (or NP-equivalent) otherwise. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： tomography discrete tomography high resolution transmission electron microscopy computational complexity polynomial-time algorithm NP-hardness #P-hardness lattice data compression image processing data security

来源：评论

学校读者我要写书评

暂无评论

algorithmic and complexity issues of three clustering methods in microarray data analysis

引用

algorithmICA 2007年第2期48卷 203-219页

作者： Tan, Jinsong Chua, Kok Seng Zhang, Louxin Zhu, Song Natl Univ Singapore Dept Math Singapore 117543 Singapore Inst High Performance Comp Singapore 117528 Singapore ST Elect Satcom & Sensor Syst Pte Ltd Singapore 609602 Singapore

The complexity, approximation and algorithmic issues of several clustering problems are studied. These non-traditional clustering problems arise from recent studies in microarray data analysis. We prove the following results. (1) Two variants of the Order-Preserving Submatrix problem are NP-hard. There are polynomial-time algorithms for the Order-Preserving Submatrix problem when the condition or gene sets are fixed. (2) Three variants of the Smooth Clustering problem are NP-hard. The Smooth Subset problem is approximable with ratio 0.5, but it cannot be approximable with ratio 0.5 + delta for any delta > 0 unless NP = P. (3) The inferring plaid model problem is NP-hard.

关键词： microarray data analysis NP-hardness approximation polynomial-time algorithm plaid model smooth clustering order-preserving submatrix

来源：评论

学校读者我要写书评

暂无评论

More results on weighted independent domination

引用

THEORETICAL COMPUTER SCIENCE 2017年 700卷 63-74页

作者： Lozin, Vadim Malyshev, Dmitriy Mosca, Raffaele Zamaraev, Viktor Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Natl Res Univ Higher Sch Econ 25-12 Bolshaya Pecherskaya Ulitsa Nizhnii Novgorod 603155 Russia Univ G DAnnunzio Dipartimento Econ I-65121 Pescara Italy

Weighted independent domination is an NP-hard graph problem, which remains computationally intractable in many restricted graph classes. In particular, the problem is NP-hard in the classes of sat-graphs and chordal graphs. We strengthen these results by showing that the problem is NP-hard in a proper subclass of the intersection of sat-graphs and chordal graphs. On the other hand, we identify two new classes of graphs where the problem admits polynomial-time solutions. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Independent domination polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Critical hereditary graph classes: a survey

引用

OPTIMIZATION LETTERS 2016年第8期10卷 1593-1612页

作者： Malyshev, D. S. Pardalos, P. M. Natl Res Univ Higher Sch Econ 25-12 Bolshaja Pecherskaja Ulitsa Nizhnii Novgorod 603155 Russia Univ Florida 401 Weil HallPOB 116595 Gainesville FL 32611 USA

The task of complete complexity dichotomy is to clearly distinguish between easy and hard cases of a given problem on a family of subproblems. We consider this task for some optimization problems restricted to certain classes of graphs closed under deletion of vertices. A concept in the solution process is based on revealing the so-called "critical" graph classes, which play an important role in the complexity analysis for the family. Recent progress in studying such classes is presented in the article.

关键词： Computational complexity polynomial-time algorithm Hereditary graph class Independent set problem Dominating set problem Coloring problem List edge-ranking problem

来源：评论

学校读者我要写书评

暂无评论

Optimal shift coloring of trees

引用

OPERATIONS RESEARCH LETTERS 2014年第4期42卷 251-256页

作者： Andreatta, Giovanni De Giovanni, Luigi Serafini, Paolo Univ Padua Dipartimento Matemat I-35121 Padua Italy Univ Udine Dipartimento Matemat & Informat I-33100 Udine Italy

This paper was motivated by the problem of scheduling the openings of pharmacies during week-ends and holiday periods (shifts). The problem can be modeled as a coloring problem on a graph. In this paper we focus on the special case where the underlying graph is a tree, or, more generally, it is endowed with a tree-metric, and we provide a polynomial-time algorithm. We also provide direct optimal solutions for special trees like stars and paths. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Graph coloring Shift coloring Trees polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximum regular induced subgraphs in 2P₃-free graphs

引用

THEORETICAL COMPUTER SCIENCE 2012年 460卷 26-33页

作者： Lozin, Vadim V. Mosca, Raffaele Univ G DAnnunzio Dipartimento Econ I-65127 Pescara Italy Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ Warwick Math Inst Coventry CV4 7AL W Midlands England

Finding maximum regular induced subgraphs is a family of algorithmic graph problems containing several important representatives such as MAXIMUM INDEPENDENT SET, MAXIMUM CLIQUE, and MAXIMUM INDUCED MATCHING. These problems are generally NP-hard. On the other hand, each of them may become polynomially solvable when restricted to graphs in special classes. However, polynomial-time solutions are available only for very few monogenic classes, i.e. classes defined by a single forbidden induced subgraph. Only three such results are available for the MAXIMUM INDEPENDENT SET and MAXIMUM CLIQUE problems and only two for the MAXIMUM INDUCED MATCHING problem. In the present paper, we extend this restricted list of results by exploring the complexity of the problems in the class of 2P(3)-free graphs, which recently attracted considerable attention in the literature. By elaborating a polynomial-time solution to the MAXIMUM INDEPENDENT SET problem in the Class Of 2K(2)-free graphs proposed by Farber in [16], we show that both MAXIMUM INDEPENDENT SET (0-regular induced subgraph) and MAXIMUM INDUCED MATCHING(1-regular induced subgraph) are solvable in polynomial time for 2P(3)-free graphs. We also conjecture that the same is true for finding maximum k-regular induced subgraphs for each value of k. On the other hand, we conjecture that finding a maximum subset of vertices inducing the complement of a k-regular induced subgraph is NP-hard for 2P(3)-free graphs and verify the conjecture for k = 0 (maximum clique), k = 1 (maximum induced co-matching), and k = 2. (c) 2012 Published by Elsevier B.V.

关键词： Independent set Clique Induced matching Regular induced subgraph polynomial-time algorithm 2P(3)-free graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：