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

Computing square roots of graphs with low maximum degree

DISCRETE APPLIED MATHEMATICS 2018年 248卷 93-101页

作者： Cochefert, Manfred Couturier, Jean-Francois Golovach, Petr A. Kratsch, Dieter Paulusma, Daniel Stewart, Anthony Univ Lorraine Lab Informat Theor & Appl F-57045 Metz 01 France IFTS CReSTIC Pole Haute Technol F-08000 Charleville Mezieres France Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England

A graph H is a square root of a graph G if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The SQUARE ROOT problem is that of deciding whether a given graph admits a square root. This problem is known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number of other graph classes. We prove that SQUARE ROOT is O(n)-time solvable for graphs of maximum degree 5 and O(n(4))-time solvable for graphs of maximum degree at most 6. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Square root Bounded degree graph polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Spanning eulerian subdigraphs in semicomplete digraphs

引用

JOURNAL OF GRAPH THEORY 2023年第3期102卷 578-606页

作者： Bang-Jensen, Jorgen Havet, Frederic Yeo, Anders Univ Southern Denmark Dept Math & Comp Sci Odense Denmark Univ Cote dAzur CNRS Projet COATI I3S Sophia Antipolis France INRIA Sophia Antipolis France

A digraph is eulerian if it is connected and every vertex has its in-degree equal to its out-degree. Having a spanning eulerian subdigraph is thus a weakening of having a hamiltonian cycle. In this paper, we first characterize the pairs (D,a) $(D,a)$ of a semicomplete digraph D $D$ and an arc a $a$ such that D $D$ has a spanning eulerian subdigraph containing a $a$. In particular, we show that if D $D$ is 2-arc-strong, then every arc is contained in a spanning eulerian subdigraph. We then characterize the pairs ( D , a ) $(D,a)$ of a semicomplete digraph D $D$ and an arc a $a$ such that D $D$ has a spanning eulerian subdigraph avoiding a $a$. In particular, we prove that every 2-arc-strong semicomplete digraph has a spanning eulerian subdigraph avoiding any prescribed arc. We also prove the existence of a (minimum) function f ( k ) $f(k)$ such that every f ( k ) $f(k)$-arc-strong semicomplete digraph contains a spanning eulerian subdigraph avoiding any prescribed set of k $k$ arcs. We conjecture that f ( k ) = k + 1 $f(k)=k+1$ and establish this conjecture for k <= 3 $k\le 3$ and when the k $k$ arcs that we delete form a forest of stars. A digraph D $D$ is eulerian-connected if for any two distinct vertices x , y $x,y$, the digraph D $D$ has a spanning ( x , y ) $(x,y)$-trail. We prove that every 2-arc-strong semicomplete digraph is eulerian-connected. All our results may be seen as arc analogues of well-known results on hamiltonian paths and cycles in semicomplete digraphs.

关键词： arc-connectivity eulerian subdigraph polynomial algorithm semicomplete digraph tournament

来源：评论

学校读者我要写书评

暂无评论

Lot sizing problem with batch ordering under periodic buyback contract and lost sales

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 2019年 208卷 500-511页

作者： Farhat, Mlouka Akbalik, Ayse Hadj-Alouane, Atidel B. Sauer, Nathalie Univ Lorraine LGIPM F-57073 Metz France Univ Lorraine LCOMS F-57073 Metz France Univ Tunis El Manar OASIS Ecole Natl Ingenieurs Tunis BP 37 Le Belvedere Tunis 1002 Tunisia

We study the deterministic single-item lot sizing problem with batch ordering under the buyback contract (LSPBB) in a system with one retailer and one supplier. We consider a fixed cost per batch replenished in addition to the classical lot sizing costs, making the procurement cost structure stepwise. We also consider lost sales option with a lost sales cost incurred for each unit of demand not satisfied. The buyback contract considered here consists in returning unused units at the end of every w periods, with a buyback revenue for each unit returned back. We study this problem under both Fn. (full truck load) cost structure and only full batch replenishment assumption. We propose efficient and exact polynomial time algorithms for different extensions of this problem which is known to be NP-hard in the general case. To the best of our knowledge, it is the first time that the buyback contract is introduced in a multi-period lot sizing problem (LSP) in the literature. Moreover, batch ordering and lost sales issues have never been tackled in the same LSP model before our study. Hence, this paper provides efficient algorithms to solve the LSP with batch ordering and lost sales under the buyback contract not yet addressed in the literature.

关键词： Lot sizing Buyback contract Batch delivery Piecewise cost polynomial algorithm Lost sales

来源：评论

学校读者我要写书评

暂无评论

L0-regularization for high-dimensional regression with corrupted data

引用

COMMUNICATIONS IN STATISTICS-THEORY AND METHODS 2024年第1期53卷 215-231页

作者： Zhang, Jie Li, Yang Zhao, Ni Zheng, Zemin Univ Sci & Technol China Sch Management Int Inst Finance Hefei 230026 Anhui Peoples R China Anhui Jianzhu Univ Sch Math & Phys Sci Hefei Anhui Peoples R China

Corrupted data appears widely in many contemporary applications including voting behavior, high-throughput sequencing and sensor networks. In this article, we consider the sparse modeling via L-0-regularization under the framework of high-dimensional measurement error models. By utilizing the techniques of the nearest positive semi-definite matrix projection, the resulting regularization problem can be efficiently solved through a polynomial algorithm. Under some interpretable conditions, we prove that the proposed estimator can enjoy comprehensive statistical properties including the model selection consistency and the oracle inequalities. In particular, the nonoptimality of the logarithmic factor of dimensionality will be showed in the oracle inequalities. We demonstrate the effectiveness of the proposed method by simulation studies.

关键词： Measurement errors L-0-regularization polynomial algorithm nearest positive semi-definite matrix projection model selection

来源：评论

学校读者我要写书评

暂无评论

A class of bottleneck expansion problems

引用

COMPUTERS & OPERATIONS RESEARCH 2001年第6期28卷 505-519页

作者： Zhang, JZ Yang, C Lin, YX City Univ Hong Kong Dept Math Hong Kong Hong Kong Peoples R China Zhengzhou Univ Dept Math Zhengzhou Peoples R China

In this paper we consider how to increase the capacities of the elements in a set E efficiently so that the capacity of a given family F of subsets of E can be increased to the maximum extent while the total cost for the increment of capacity is within a given budget bound. We transform this problem into finding the minimum weight element of F when the weight of each element of E is a linear function of a single parameter and propose an algorithm for solving this problem. We further discuss the problem for some special cases. Especially, when E is the edge set of a network and the family F consists of all spanning trees, we give a strongly polynomial algorithm.

关键词： bottleneck problem inverse optimization problem minimum-weight element problem parametric linear programming polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

DOMINATION IN CONVEX AND CHORDAL BIPARTITE GRAPHS

引用

INFORMATION PROCESSING LETTERS 1990年第5期36卷 231-236页

作者： DAMASCHKE, P MULLER, H KRATSCH, D Friedrich-Schiller-Univ. Sekt. Math. Universitaetshochhaus DDR 6900 Jena GDR

The authors state that various domination problems are polynomial time solvable in convex bipartite graphs, and we give the main ideas of the algorithms. Total Dominating Set is polynomial even for chordal bipartite graphs. Further, it is shown by a reduction from 3SAT that Independent Dominating Set remain NP-complete when restricted to chordal bipartite graphs.

关键词： Domination polynomial algorithm NP-completeness restricted classes of bipartite graphs

来源：评论

学校读者我要写书评

暂无评论

Non-linear integer programming by Darwin and Boltzmann mixed strategy

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1998年第1期105卷 224-235页

作者： Tian, P Ma, J Zhang, DM City Univ Hong Kong Dept Informat Syst Kowloon Hong Kong Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai 200030 Peoples R China

Non-linear integer programming (NIP) is a NP-complete problem with extensive theoretical and practical backgrounds. Based on our proposed Darwin and Boltzmann mixed strategy, this paper presents a general stochastic iterative algorithm for the NIP problems. The algorithm synthesizes the advantages of the Darwin strategy and the Boltzmann annealing strategy. It converges asymptotically to the global optimums and has shown to be polynomial in complexity. The experimental evaluations also show that the proposed algorithm is more efficient than the simulated annealing algorithm. (C) 1998 Elsevier Science B.V.

关键词： optimization non-linear integer programming Darwin and Boltzmann mixed strategy global convergence polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

2 algorithmS FOR WEIGHTED MATROID INTERSECTION

引用

MATHEMATICAL PROGRAMMING 1986年第1期36卷 39-53页

作者： BREZOVEC, C CORNUEJOLS, G GLOVER, F UNIV COLORADO BOULDERCO 80309

Consider a finite setE, a weight functionw:E→R, and two matroidsM 1 andM 2 defined onE. The weighted matroid intersection problem consists of finding a setI⊆E, independen... 详细信息

Consider a finite setE, a weight functionw:E→R, and two matroidsM 1 andM 2 defined onE. The weighted matroid intersection problem consists of finding a setI⊆E, independent in both matroids, that maximizes Σ{w(e):e inI}. We present an algorithm of complexity O(nr(r+c+logn)) for this problem, wheren=|E|,r=min(rank(M 1), rank (M 2)),c=max (c 1,c 2) and, fori=1,2,c i is the complexity of finding the circuit ofI∪{e} inM i (or show that none exists) wheree is inE andI⊆E is independent inM 1 andM 2. A related problem is to find a maximum weight set, independent in both matroids, and of given cardinalityk (if one exists). Our algorithm also solves this problem. In addition, we present a second algorithm that, given a feasible solution of cardinalityk, finds an optimal one of the same cardinality. A sensitivity analysis on the weights is easy to perform using this approach. Our two algorithms are related to existing algorithms. In fact, our framework provides new simple proofs of their validity. Other contributions of this paper are the existence of nonnegative reduced weights (Theorem 6), allowing the improved complexity bound, and the introduction of artificial elements, allowing an improved start and flexibility in the implementation of the algorithms.

关键词： matroid intersection algorithm Matroids polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

The minimum spanning strong subdigraph problem for extended semicomplete digraphs and semicomplete bipartite digraphs

引用

JOURNAL OF algorithmS-COGNITION INFORMATICS AND LOGIC 2001年第1期41卷 1-19页

作者： Bang-Jensen, J Yeo, A Odense Univ Dept Math & Comp Sci DK-5230 Odense Denmark Aarhus Univ Dept Comp Sci BRICS DK-8000 Aarhus Denmark Univ Victoria Dept Math & Stat Victoria BC V8W 2Y2 Canada

We consider the problem (minimum spanning strong subdigraph (MSSS)) of finding the minimum number of arcs in a spanning strongly connected subdigraph of a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the Hamiltonian cycle problem. We characterize the number of arcs in a minimum spanning strong subdigraph for digraphs which are either extended semicomplete or semicomplete bipartite. Our proofs lead to polynomial algorithms for finding an optimal subdigraph for every digraph from each of these classes. Our proofs are based on a number of results (some of which are new and interesting in their own right) on the structure of cycles and paths in these graphs. Recently, it was shown that the Hamiltonian cycle problem is polynomially solvable for semicomplete multipartite digraphs, a superclass of the two classes above [15]. We conjecture that the MSSS problem is also polynomial for this class of digraphs. (C) 2001 Academic Press.

关键词： minimum equivalent digraph Hamiltonian path Hamiltonian cycle polynomial algorithm locally semicomplete digraphs path-mergeable digraph multipartite tournament semicomplete multipartite digraph cycle factor path covering

来源：评论

学校读者我要写书评

暂无评论

Finding complementary cycles in locally semicomplete digraphs

引用

DISCRETE APPLIED MATHEMATICS 2005年第3期146卷 245-256页

作者： Bang-Jensen, J Nielsen, MH Univ So Denmark Dept Math & Comp Sci DK-5230 Odense Denmark

It is well known that the problem of deciding whether a given digraph has a k-cycle factor for some constant k (i.e. a collection of k disjoint cycles that cover all vertices of the digraph) is N P-complete as this is a generalization of the Hamilton cycle problem. In this paper, we show that for the class of locally semicomplete digraphs the existence of a 2-cycle factor can be decided, and a 2-cycle factor found if it exists, in time O(n(3)), where n is the order of the digraph. (C) 2004 Elsevier B.V. All rights reserved.

关键词： complementary cycles 2-cycle factor locally semicomplete digraph semicomplete digraph polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：