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

(1,1)-Cluster Editing is polynomial-time solvable

DISCRETE APPLIED MATHEMATICS 2023年第1期340卷 259-271页

作者： Gutin, Gregory Yeo, Anders Royal Holloway Univ London Dept Comp Sci London England Univ Southern Denmark Dept Math & Comp Sci Odense Denmark Univ Johannesburg Dept Pure & Appl Math Johannesburg South Africa

A graph H is a clique graph if H is a vertex-disjoin union of cliques. Abu-Khzam (2017) introduced the (a, d)-Cluster Editing problem, where for fixed natural numbers a, d, given a graph G and vertex-weights a* : V(G) {0, 1, ... , a} and d* : V(G) {0, 1, ... , d}, we are to decide whether G can be turned into a cluster graph by deleting at most d*(v) edges incident to every v & ISIN;V(G) and adding at most a*(v) edges incident to every v & ISIN;V(G). Results by Komusiewicz and Uhlmann (2012) and Abu-Khzam (2017) provided a dichotomy of complexity (in P or NP-complete) of (a, d)-Cluster Editing for all pairs a, d apart from a = d = 1. Abu-Khzam (2017) conjectured that (1, 1)-Cluster Editing is in P. We resolve Abu-Khzam's conjecture in affirmative by (i) providing a series of five polynomial-time reductions to C3-free and C4-free graphs of maximum degree at most 3, and (ii) designing a polynomial-time algorithm for solving (1, 1)-Cluster Editing on C3-free and C4-free graphs of maximum degree at most 3.& COPY;2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Cluster editing polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Packing cycles exactly in polynomial time

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2012年第2期23卷 167-188页

作者： Chen, Qin Chen, Xujin Chinese Acad Sci Inst Appl Math Beijing 100190 Peoples R China Univ Hong Kong Dept Math Hong Kong Hong Kong Peoples R China

Let G = (V, E) be an undirected graph in which every vertex v. V is assigned a nonnegative integer w(v). A w- packing is a collection P of cycles (repetition allowed) in G such that every v. V is contained at most w(v) times by the members of P. Let < w > = 2|V | + Sigma(v is an element of V)[log(w(v)+ 1)] denote the binary encoding length (input size) of the vector (w(v): v is an element of V)(T). We present an efficient algorithm which finds in O(|V|(8) < w >(2) + |V|(14)) time a w- packing of maximum cardinality in G provided packing and covering cycles inGsatisfy the Z(+)-max-flow min-cut property.

关键词： Packing and covering polynomial algorithm Min-max relation Maximum cycle packing

来源：评论

学校读者我要写书评

暂无评论

The longest cycle problem is polynomial on interval graphs

引用

THEORETICAL COMPUTER SCIENCE 2021年 859卷 37-47页

作者： Shang, Jianhui Li, Peng Shi, Yi Shanghai Jiao Tong Univ Sch Math Sci Shanghai 200240 Peoples R China Chongqing Univ Technol Coll Sci Chongqing 400054 Peoples R China Shanghai Jiao Tong Univ Bio X Inst Key Lab Genet Dev & Neuropsychiat Disorders Minist Educ 1954 Huashan Rd Shanghai 200030 Peoples R China

The longest cycle problem is the problem of finding a cycle with maximal vertices in a graph. Although it is solvable in polynomial time on few trivial graph classes, the longest cycle problem is well known as NP-complete. A lot of efforts have been devoted to the longest cycle problem. To the best of our knowledge however, there are no polynomial algorithms that can solve any of the non-trivial graph classes. Interval graphs, the intersection of chordal graphs and asteroidal triple-free graphs, are known to be the non-trial graph classes that have polynomial algorithm of the longest cycle problem. In 2009, K. Ioannidou, G.B. Mertzios and S.D. Nikolopoulos presented a polynomial algorithm for the longest path problem on interval graphs in Ioannidou et al. (2009) [19]. Inspired by their work, we investigate the longest cycle problem of interval graphs. In this paper, we present the first polynomial algorithm for the longest cycle problem on interval graphs. A dynamic programming approach is proposed in the polynomial algorithm that runs in O(n(8)) time, where n is the number of vertices of the input graph. Using a similar approach, we design a polynomial algorithm to solve the longest k-thick subgraph problem on interval graphs which will be presented in another separate work. According to the interesting properties of k-thick interval graphs that we discovered (e.g., an interval graph G is traceable if and only if G is 1-thick, G is hamiltonian if and only if G is 2-thick, G is hamiltonian connected if and only if G is 3-thick and so on), the algorithm presented in this paper can be important in studying the spanning connectivity on interval graphs. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Longest cycle problem Interval graphs The k-thick graphs polynomial algorithm Dynamic programming Longest path problem

来源：评论

学校读者我要写书评

暂无评论

The Longest Path Problem has a polynomial Solution on Interval Graphs

引用

algorithmICA 2011年第2期61卷 320-341页

作者： Ioannidou, Kyriaki Mertzios, George B. Nikolopoulos, Stavros D. Univ Ioannina Dept Comp Sci GR-45110 Ioannina Greece Rhein Westfal TH Aachen Dept Comp Sci D-52074 Aachen Germany

The longest path problem is the problem of finding a path of maximum length in a graph. polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian path problem. Motivated by the work of Uehara and Uno (Proc. of the 15th Annual International Symp. on algorithms and Computation (ISAAC), LNCS, vol. 3341, pp. 871-883, 2004), where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem can be solved in polynomial time on interval graphs. The proposed algorithm uses a dynamic programming approach and runs in O(n (4)) time, where n is the number of vertices of the input graph.

关键词： Longest path problem Interval graphs polynomial algorithm Complexity Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

polynomial Asymptotically Optimal Coding of Underdetermined Bernoulli Sources of the General Form

引用

PROBLEMS OF INFORMATION TRANSMISSION 2020年第4期56卷 373-387页

作者： Sholomov, L. A. Russian Acad Sci Fed Res Ctr Comp Sci & Control Moscow Russia Russian Acad Sci Inst Syst Anal Moscow Russia

An underdetermined Bernoulli source generates symbols of a given underdetermined alphabet independently with some probabilities. To each underdetermined symbol there corresponds a set of basic (fully defined) symbols such that it can be substituted (specified) by any of them. An underdetermined source is characterized by its entropy, which is implicitly introduced as a minimum of a certain function and plays a role similar to the Shannon entropy for fully defined sources. Coding of an underdetermined source must ensure, for any sequence generated by the source, recovering some its specification. Coding is asymptotically optimal if the average code length is asymptotically equal to the source entropy. Coding is universal if it does not depend on the probabilities of source symbols. We describe an asymptotically optimal universal coding method for underdetermined Bernoulli sources for which the encoding and decoding procedures can be realized by RAM-programs of almost linear complexity.

关键词： underdetermined source specification entropy of an underdetermined source quasientropy of a word combinatorial entropy of a class underdetermined source coding universal coding polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Colorful edge decomposition of graphs: Some polynomial cases

引用

DISCRETE APPLIED MATHEMATICS 2017年 231卷 155-165页

作者： Dehghan, Ali Sadeghi, Mohammad-Reza Carleton Univ Syst & Comp Engn Dept Ottawa ON Canada Amirkabir Univ Technol Dept Math & Comp Sci Tehran Iran

Consider a graph G and a labeling of its edges with r labels. Every vertex v is an element of V(G) is associated with a palette of incident labels together with their frequencies, which sum up to the degree of v. We say that two vertices have distinct palettes if they differ in the frequency of at least one label, otherwise they have the same palette. For an integer r > 0, a colorful r-edge decomposition of a graph G is a labeling l : E(G) -> {1, . . . , r} such that for any vertex v is an element of V(G), the edges incident with the vertex v have at least min{r, d(v)} different labels and for every two adjacent vertices v and u with d(v) = d(u), they have the same palette. In this work, we investigate some properties of this edge decomposition. We prove that for each t, every tree has a colorful t-edge decomposition and that decomposition can be found in polynomial time. On the negative side, we prove that for a given graph G with 2 <= delta(G) <= Delta(G) <= 3 determining whether G has a colorful 2-edge decomposition is NP-complete. Among other results, we show that for a given bipartite graph G with degree set {a(1), a(2), . . . , a(c)} where c is a constant number, if for each i, 1 <= i <= c, the induced subgraph on the set of vertices of degree a(i) has d connected components, where d is a constant number, then there is a polynomial time algorithm to decide whether G has a colorful 2-edge decomposition. Also, we prove that every r-regular graph G with at most one cut edge has a colorful 2-edge decomposition. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Colorful edge decomposition Palette Graph decomposition Totally unimodular matrix polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

A polynomial-TIME DESCENT METHOD FOR SEPARABLE CONVEX OPTIMIZATION PROBLEMS WITH LINEAR CONSTRAINTS

引用

SIAM JOURNAL ON OPTIMIZATION 2016年第1期26卷 856-889页

作者： Chubanov, Sergei Univ Siegen Fac Econ D-57068 Siegen Germany

We propose a polynomial algorithm for a separable convex optimization problem with linear constraints. We do not make any additional assumptions about the structure of the objective function except for polynomial computability. That is, the objective function can be non-differentiable. The running time of our algorithm is polynomial in the size of the input consisting of an instance of the problem and the accuracy with which the problem is to be solved. Our algorithm uses an oracle for solving auxiliary systems of linear inequalities. This oracle can be any polynomial algorithm for linear programming.

关键词： convex optimization separable convex function polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming

引用

NUMERICAL algorithmS 2018年第3期79卷 957-992页

作者： Yang, Y. US NRC Off Res Two White Flint North 11545 Rockville Pike Rockville MD 20852 USA

Since the beginning of the development of interior-point methods, there exists a puzzling gap between the results in theory and the observations in numerical experience, i.e., algorithms with good polynomial bounds are not computationally efficient and algorithms demonstrated efficiency in computation do not have a good or any polynomial bound. Todd raised a question in 2002: Can we find a theoretically and practically efficient way to reoptimize? This paper is an effort to close the gap. We propose two arc-search infeasible interior-point algorithms with infeasible central path neighborhood wider than all existing infeasible interior-point algorithms that are proved to be convergent. We show that the first algorithm is polynomial and its simplified version has a complexity bound equal to the best known complexity bound for all (feasible or infeasible) interior-point algorithms. We demonstrate the computational efficiency of the proposed algorithms by testing all Netlib linear programming problems in standard form and comparing the numerical results to those obtained by Mehrotra's predictor-corrector algorithm and a recently developed more efficient arc-search algorithm (the convergence of these two algorithms is unknown). We conclude that the newly proposed algorithms are not only polynomial but also computationally competitive compared to both Mehrotra's predictor-corrector algorithm and the efficient arc-search algorithm.

关键词： polynomial algorithm Arc-search Infeasible interior-point method Linear programming

来源：评论

学校读者我要写书评

暂无评论

polynomial instances of the positive semidefinite and Euclidean distance matrix completion problems

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2000年第3期22卷 874-894页

作者： Laurent, M CWI NL-1090 GB Amsterdam Netherlands

Given an undirected graph G = (V, E) with node set V = [1, n], a subset S subset of or equal to V, and a rational vector a is an element ofQ(S boolean ORE), the positive semidefinite matrix completion problem consists of determining whether there exists a real symmetric n x n positive semidefinite matrix X = (x(ij)) satisfying x(ii) = a(i) (i is an element of S) and x(ij) = a(ij) (ij is an element of E). Similarly, the Euclidean distance matrix completion problem asks for the existence of a Euclidean distance matrix completing a partially defined given matrix. It is not known whether these problems belong to NP. We show here that they can be solved in polynomial time when restricted to the graphs having a fixed minimum fill-in,the minimum fill-in of graph G being the minimum number of edges needed to be added to G in order to obtain a chordal graph. A simple combinatorial algorithm permits us to construct a completion in polynomial time n the chordal case. We also show that the completion problem is polynomially solvable for a class of graphs including wheels of fixed length ( assuming all diagonal entries are specified). The running time of our algorithms is polynomially bounded in terms of n and the bitlength of the input a. We also observe that the matrix completion problem can be solved in polynomial time n the real number model for the class of graphs containing no homeomorph of K-4.

关键词： positive semidefinite matrix Euclidean distance matrix matrix completion chordal graph minimum fill-in order of a graph polynomial algorithm bit model real number model

来源：评论

学校读者我要写书评

暂无评论

The Frobenius problem for classes of polynomial solvability

引用

MATHEMATICAL NOTES 2001年第5-6期70卷 771-778页

作者： Kan, ID Moscow MV Lomonosov State Univ Moscow 117234 Russia

The Frobenius problem is to find a method (= algorithm) for calculating the largest "sum of money" that cannot be given by coins whose values b(0), b(1),..., b(w). are coprime integers. As admissible solutions (algorithms), it is common practice to study polynomial algorithms, which owe their name to the form of the dependence of time expenditure on the length of the original information. The difficulty of the Frobenius problem is apparent from the fact that already for w = 3 the existence of a polynomial solution is still an open problem. In the present paper, we distinguish some classes of input data for which the problem can be solved polynomially;nevertheless, argumentation in the spirit of complexity theory of algorithms is kept to a minimum.

关键词： Frobenius problem coprime integers polynomial algorithm Johnson algorithm Rodset algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：