共查询到20条相似文献,搜索用时 15 毫秒
1.
W. Kook 《Discrete Mathematics》2005,300(1-3):235-238
Given a matroid M and its Tutte polynomial TM(x,y), TM(0,1) is an invariant of M with various interesting combinatorial and topological interpretations. Being a Tutte–Grothendieck invariant, TM(0,1) may be computed via deletion–contraction recursions. In this note we derive a new recursion formula for this invariant that involves contractions of M through the circuits containing a fixed element of M. 相似文献
2.
Theoretical results pertaining to the independent set polytope PISP=conv{x{0,1}n:Axb} are presented. A conflict hypergraph is constructed based on the set of dependent sets which facilitates the examination of the facial structure of PISP. Necessary and sufficient conditions are provided for every nontrivial 0-1 facet-defining inequalities of PISP in terms of hypercliques. The relationship of hypercliques and some classes of knapsack facet-defining inequalities are briefly discussed. The notion of lifting is extended to the conflict hypergraph setting to obtain strong valid inequalities, and back-lifting is introduced to strengthen cut coefficients. Preliminary computational results are presented to illustrate the usefulness of the theoretical findings.Mathematics Subject Classification (2000): 90C11, 90C57, 90C35 相似文献
3.
In this paper, we present an O(r
4
n) algorithm for the linear matroid parity problem. Our solution technique is to introduce a modest generalization, the non-simple parity problem, and identify an important subclass of non-simple parity problems called easy parity problems which can be solved as matroid intersection problems. We then show how to solve any linear matroid parity problem parametrically as a sequence of easy parity problems.In contrast to other algorithmic work on this problem, we focus on general structural properties of dual solutions rather than on local primal structures. In a companion paper, we develop these ideas into a duality theory for the parity problem. 相似文献
4.
A submodular polyhedron is a polyhedron associated with a submodular function. This paper presents a strongly polynomial time algorithm for line search in submodular polyhedra with the aid of a fully combinatorial algorithm for submodular function minimization. The algorithm is based on the parametric search method proposed by Megiddo. 相似文献
5.
This paper presents a faster algorithm for the M-convex submodular flow problem, which is a generalization of the minimum-cost flow problem with an M-convex cost function for the flow-boundary, where an M-convex function is a nonlinear nonseparable discrete convex function on integer points. The algorithm extends the capacity scaling approach for the submodular flow problem by Fleischer, Iwata and McCormick (2002) with the aid of a novel technique of changing the potential by solving maximum submodular flow problems.Mathematics Subject Classification (1991): 90C27A preliminary version of this paper has appeared in Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization (IPCO X), LNCS 3064, Springer-Verlag, 2004, pp. 352–367. 相似文献
6.
7.
Ludwin A.BASILIO-HERNáNDEZ Walter CARBALLOSA Jesús LEA?OS José M.SIGARRETA 《数学学报(英文版)》2019,35(3):338-354
We introduce the differential polynomial of a graph. The differential polynomial of a graph G of order n is the polynomial B(G; x) :=∑?(G)k=-nB_k(G) x~(n+k), where B_k(G) denotes the number of vertex subsets of G with differential equal to k. We state some properties of B(G;x) and its coefficients.In particular, we compute the differential polynomial for complete, empty, path, cycle, wheel and double star graphs. We also establish some relationships between B(G; x) and the differential polynomials of graphs which result by removing, adding, and subdividing an edge from G. 相似文献
8.
A set S of vertices in a graph H=(V,E) with no isolated vertices is a paired-dominating set of H if every vertex of H is adjacent to at least one vertex in S and if the subgraph induced by S contains a perfect matching. Let G be a permutation graph and π be its corresponding permutation. In this paper we present an O(mn) time algorithm for finding a minimum cardinality paired-dominating set for a permutation graph G with n vertices and m edges. 相似文献
9.
对向量的秩与最大无关组的教学过程进行了分析研究,从教学内容组织与教学手段等方面提出了改革的方案.对有的教材的不足提出了改进办法. 相似文献
10.
Pawel Winter 《BIT Numerical Mathematics》1986,26(1):44-62
Enumeration of spanning trees of an undirected graph is one of the graph problems that has received much attention in the literature. In this paper a new enumeration algorithm based on the idea of contractions of the graph is presented. The worst-case time complexity of the algorithm isO(n+m+nt) wheren is the number of vertices,m the number of edges, andt the number of spanning trees in the graph. The worst-case space complexity of the algorithm isO(n
2). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms. 相似文献
11.
A. R. Mahjoub 《Mathematical Programming》1988,40(1-3):53-57
We give a short proof of Chvátal's conjecture that the nontrivial facets of the stable set polytope of a series-parallel graph all come from edges and odd holes.Research supported in part by the Natural Sciences and Engineering Research Council of Canada and by CP Rail. 相似文献
12.
In 1985, Erdős and Nešetřil conjectured that the square of the line graph of a graph , that is, , can be colored with colors. This conjecture implies the weaker conjecture that the clique number of such a graph, that is, , is at most . In 2015, Śleszyńska-Nowak proved that . In this paper, we prove that . This theorem follows from our stronger result that where . 相似文献
13.
Yeh (2001) [W.-C. Yeh, A simple algorithm for the planar multiway cut problem, J. Algorithms 39 (2001) 68-77] described a simple algorithm with time complexity for the planar minimum k-terminal cut problem. In this paper, an example showing that the algorithm could fail to return a minimum k-cut is given. 相似文献
14.
Andrew D. King 《Journal of Graph Theory》2011,67(4):300-305
Rabern recently proved that any graph with contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exists for any graph with . This is tight, i.e. the inequality in the statement must be strict. The proof relies on finding an independent transversal in a graph partitioned into vertex sets of unequal size. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:300‐305, 2011 相似文献
15.
16.
Heuristic algorithms for scheduling tasks with multiple modes and minimizing the schedule length involve in general two distinct
phases, task mode assignment and then task scheduling. We propose a novel approach where these two features are managed in an integrated mechanism with mode assignment embedded
in scheduling. The problem is first reformulated as a special single-mode task scheduling problem, and then is modeled as
a graph interval T-coloring. Finally, a tabu-like metaheuristic is proposed for this latter graph coloring problem, and the performance of our
approach is compared to known multi-mode scheduling heuristics. 相似文献
17.
Richard T. Wong 《Mathematical Programming》1984,28(3):271-287
The Steiner tree problem on a directed graph (STDG) is to find a directed subtree that connects a root node to every node
in a designated node setV. We give a dual ascent procedure for obtaining lower bounds to the optimal solution value. The ascent information is also
used in a heuristic procedure for obtaining feasible solutions to the STDG. Computational results indicate that the two procedures
are very effective in solving a class of STDG's containing up to 60 nodes and 240 directed/120 undirected arcs.
The directed spanning tree and uncapacitated plant location problems are special cases of the STDG. Using these relationships,
we show that our ascent procedure can be viewed as a generalization ofboth the Chu-Liu-Edmonds directed spanning tree algorithm and the Bilde-Krarup-Erlenkotter ascent algorithm for the plant location
problem. The former comparison yields a dual ascent interpretation of the steps of the directed spanning tree algorithm. 相似文献
18.
19.
Maria Emilia M.T. Walter Mauro C. Sobrinho Eugenia T.G. Oliveira Lorena S. Soares Adilton G. Oliveira Thelmo E.S. Martins Tiago M. Fonseca 《Journal of Discrete Algorithms》2005,3(2-4):342-361
In computational biology, genome rearrangements is a field in which we investigate the combinatorial problem of sorting by transpositions. This problem consists in finding the minimum number of transpositions (mutational event) that transform a chromosome into another. Bafna and Pevzner [SIAM J. 11 (2) (1998) 224–240] proposed a 1.5-approximation algorithm to solve this problem, using a structure called cycle graph. In this work, we first present results that allowed us to implement their algorithm, maintaining the 1.5-approximation ratio. The present implementation runs in O(n3) time complexity, noting that we created a data structure to store the cycle graph in memory in O(n) time complexity. The results obtained from the program allowed us to propose heuristics, that further improved the performance of the original algorithm. Comparing our experimental results with the best results published so far, we achieved better performance. Besides, we developed a program to visualize the cycle graphs and the transpositions indicated by the algorithm. This work targets to contribute for discovering the complexity of the problem of sorting by transpositions, which remains open. 相似文献
20.
Johannes H. Hattingh 《Discrete Applied Mathematics》2009,157(13):2846-2858
Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γr(G), is the smallest cardinality of a restrained dominating set of G. We will show that if G is a connected graph of order n and minimum degree δ and not isomorphic to one of nine exceptional graphs, then . 相似文献