共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
3.
An algorithm is presented for finding annth-best spanning tree of an edge-weighted graphG. In sharp contrast to related ranking algorithms, the number of steps is a linear function of the parametern. The results apply as well to ranking the bases of an abstract matroid. 相似文献
4.
5.
6.
The Minimum Score Separation Problem (MSSP) is a combinatorial problem that was introduced in JORS 55 as an open problem in the paper industry arising in conjunction with the cutting stock problem. During the process of producing boxes, flat papers are prepared for folding by being scored with knives. The problem is to determine whether and how a given production pattern of boxes can be arranged such that a certain minimum distance between the knives can be kept. Introducing the concept of matching-based alternating Hamiltonian paths, this paper models the MSSP as the problem of finding an alternating Hamiltonian path on a graph that is the union of a matching and a type of graph known as a ‘threshold graph’. On this basis, we find a heuristic that can quickly recognize a large percentage of feasible and infeasible instances of the MSSP. Detailed computational experiments demonstrate the efficiency of our approach. 相似文献
7.
8.
《Discrete Mathematics》2023,346(1):113151
The Plurality problem - introduced by Aigner - has many variants. In this article we deal with the following version: suppose we are given n balls, each of them colored by one of three colors. A plurality ball is one such that its color class is strictly larger than any other color class. Questioner asks a triplet (or a k-set in general), and Adversary as an answer gives the partition of the triplet (or the k-set) into color classes. Questioner wants to find a plurality ball as soon as possible or show that there is no such ball, while Adversary wants to postpone this.We denote by the largest number of queries needed to ask in the worst case if both play optimally. We provide an almost precise result in the case of even n by proving that for even we have and for odd we haveWe also prove some bounds on the number of queries needed to ask in the case . 相似文献
9.
We give a generalization of a result of Myerson on the asymptoticbehavior of norms of certain Gaussian periods. The proof exploitsproperties of the Mahler measure of a trinomial. 相似文献
10.
《European Journal of Operational Research》1999,115(2):339-350
We study the two-group classification problem which involves classifying an observation into one of two groups based on its attributes. The classification rule is a hyperplane which misclassifies the fewest number of observations in the training sample. Exact and heuristic algorithms for solving the problem are presented. Computational results confirm the efficiency of this approach. 相似文献
11.
In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x1,x2,…,xk?nk there exist k distinct integers j1,j2,…,jk so that xi= aii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k). 相似文献
12.
In this paper we present an algorithm based on network flow techniques which provides a solution for a combinatorial problem. Then, in order to provide all the solutions of this problem, we make use of an algorithm that given the bipartite graphG=(V 1 ∪V 2,E, w) outputs the enumeration of all bipartite matchings of given cardinalityv and costc. 相似文献
13.
A tutorial outline of the polyhedral theory that underlies linear programming (LP)-based combinatorial problem solving is given. Design aspects of a combinatorial problem solver are discussed in general terms. Three computational studies in combinatorial problem solving using the polyhedral theory developed in the past fifteen years are surveyed: one addresses the symmetric traveling salesman problem, another the optimal triangulation of input/output matrices, and the third the optimization of large-scale zero-one linear programming problems. 相似文献
14.
We further generalise a construction–the fibre construction–that was developed in an earlier paper of the first two authors. The extension in this paper gives a polynomial-time reduction of for any relational system H to for any relational system P that meets a certain technical partition condition, that of being K3-partitionable.Moreover, we define an equivalent condition on P, that of being block projective, and using this show that our construction proves NP-completeness for exactly those CSPs that are conjectured to be NP-complete by the CSP dichotomy classification conjecture made by Bulatov, Jeavons and Krohkin, and by Larose and Zádori. We thus provide two new combinatorial versions of the dichotomy classification conjecture.As with our previous version of the fibre construction, we are able to address restricted versions of the dichotomy conjecture. In particular, we reduce the Feder–Hell–Huang conjecture to the dichotomy classification conjecture, and we prove the Kostochka–Nešetřil–Smolíková conjecture. Although these results were proved independently by Jonsson et al. and Kun respectively, we give different, shorter, proofs. 相似文献
15.
16.
“关于不可约弱广义对角优势阵”一文的注记 总被引:7,自引:0,他引:7
指出标题所述的论文(见《数学理论与应用》2000年20卷2期)中的错误,分析了产生错误的原因,并给出修正的结果,得到了一类M-矩阵的新表征。 相似文献
17.
On a problem of partitions of the set of nonnegative integers with the same representation functions
Dombi has shown that the set of all non-negative integers can be partitioned into two subsets with identical representation functions. In this paper, we prove that one cannot partition into more than two subsets with identical representation functions, while for any integer there is a partition such that and have the same representation function for any integer . 相似文献
18.
19.
A. K. Agarwal 《Journal of Computational and Applied Mathematics》2003,160(1-2):9-15
An analogue of Euler's partition identity: “The number of partitions of a positive integer ν into odd parts equals the number of its partitions into distinct parts” is obtained for ordered partitions. The ideas developed are then used in obtaining several new combinatorial properties of the n-colour compositions introduced recently by the author. 相似文献
20.
An-Chiang Chu 《Discrete Applied Mathematics》2010,158(14):1471-1478
In this paper, we study how to partition a tree into edge-disjoint subtrees of approximately the same size. Given a tree T with n edges and a positive integer k≤n, we design an algorithm to partition T into k edge-disjoint subtrees such that the ratio of the maximum number to the minimum number of edges of the subtrees is at most two. The best previous upper bound of the ratio is three, given by Wu et al. [B.Y. Wu, H.-L. Wang, S.-T. Kuan, K.-M. Chao, On the uniform edge-partition of a tree, Discrete Applied Mathematics 155 (10) (2007) 1213-1223]. Wu et al. also showed that for some instances, it is impossible to achieve a ratio better than two. Therefore, there is a lower bound of two on the ratio. It follows that the ratio upper bound attained in this paper is already tight. 相似文献