共查询到20条相似文献,搜索用时 15 毫秒
1.
In this paper, we study the connected subgraph polytope which is the convex hull of the solutions to a related combinatorial optimization problem called the maximum weight connected subgraph problem. We strengthen a cut-based formulation by considering some new partition inequalities for which we give necessary and sufficient conditions to be facet defining. Based on the separation problem associated with these inequalities, we give a complete polyhedral characterization of the connected subgraph polytope on cycles and trees. 相似文献
2.
We consider the minimum rainbow subgraph problem (MRS): given a graph G, whose edges are coloured with p colours. Find a subgraph F⊆G of G of minimum order and with p edges such that each colour occurs exactly once. For graphs with maximum degree Δ(G) there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of Δ(G). In this paper we present a polynomial-time approximation algorithm with an approximation ratio of for Δ≥2. 相似文献
3.
In this paper we present an exact algorithm for the Maximum Common Induced Subgraph Problem (MCIS) by addressing it directly, using Integer Programming (IP) and polyhedral combinatorics. We study the MCIS polytope and introduce strong valid inequalities, some of which we prove to define facets. Besides, we show an equivalence between our IP model for MCIS and a well-known formulation for the Maximum Clique problem. We report on computational results of branch-and-bound (B&B) and branch-and-cut (B&C) algorithms we implemented and compare them to those yielded by an existing combinatorial algorithm. 相似文献
4.
CHENHUAITANG MAKEJIE 《高校应用数学学报(英文版)》1998,13(2):165-170
The definition of the ascending suhgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition. 相似文献
5.
Tomislav Došli? 《Discrete Applied Mathematics》2007,155(10):1294-1301
Bipartite edge frustration of a graph is defined as the smallest number of edges that have to be deleted from the graph to obtain a bipartite spanning subgraph. We show that for fullerene graphs this quantity can be computed in polynomial time and obtain explicit formulas for the icosahedral fullerenes. We also report some computational results and discuss a potential application of this invariant in the context of fullerene stability. 相似文献
6.
7.
We present a simple 3-approximation algorithm for the feedback vertex set problem in a bipartite tournament, improving on the approximation ratio of 3.5 achieved by the best previous algorithms. 相似文献
8.
In this paper we study the extreme points of the polytope P(G), the linear relaxation of the 2-edge connected spanning subgraph polytope of a graph G. We introduce a partial ordering on the extreme points of P(G) and give necessary conditions for a non-integer extreme point of P(G) to be minimal with respect to that ordering. We show that, if is a non-integer minimal extreme point of P(G), then G and can be reduced, by means of some reduction operations, to a graph G' and an extreme point of P(G') where G' and satisfy some simple properties. As a consequence we obtain a characterization of the perfectly 2-edge connected graphs, the
graphs for which the polytope P(G) is integral.
Received: May, 2004
Part of this work has been done while the first author was visiting the Research Institute for Discrete Mathematics, University
of Bonn, Germany. 相似文献
9.
Andreas Brandstädt 《Discrete Mathematics》2009,309(12):3843-910
A graph G is a k-leaf power if there is a tree T such that the vertices of G are the leaves of T and two vertices are adjacent in G if and only if their distance in T is at most k. In this situation T is called a k-leaf root of G. Motivated by the search for underlying phylogenetic trees, the notion of a k-leaf power was introduced and studied by Nishimura, Ragde and Thilikos and subsequently in various other papers. While the structure of 3- and 4-leaf powers is well understood, for k≥5 the characterization of k-leaf powers remains a challenging open problem.In the present paper, we give a forbidden induced subgraph characterization of distance-hereditary 5-leaf powers. Our result generalizes known characterization results on 3-leaf powers since these are distance-hereditary 5-leaf powers. 相似文献
10.
We consider the sandwich problem, a generalization of the recognition problem introduced by Golumbic et al. (1995) [15], with respect to classes of graphs defined by excluding induced subgraphs. We prove that the sandwich problem corresponding to excluding a chordless cycle of fixed length k is NP-complete. We prove that the sandwich problem corresponding to excluding Kr?e for fixed r is polynomial. We prove that the sandwich problem corresponding to 3PC(⋅,⋅)-free graphs is NP-complete. These complexity results are related to the classification of a long-standing open problem: the sandwich problem corresponding to perfect graphs. 相似文献
11.
《Discrete Mathematics》2022,345(5):112799
We prove that among connected graphs of order n, the path uniquely minimises the average order of its connected induced subgraphs. This confirms a conjecture of Kroeker, Mol and Oellermann, and generalises a classical result of Jamison for trees, as well as giving a new, shorter proof of the latter.A different proof of the main result was given independently and almost simultaneously by Andrew Vince; the two preprints were submitted one day apart. 相似文献
12.
Given a bipartite graph G=(V,E), a weight for each node, and a weight for each edge, we consider an extension of the MAX-CUT problem that consists in searching for a partition of V into two subsets V1 and V2 such that the sum of the weights of the edges from E that have one endpoint in each set plus the sum of the weights of the nodes from V that are in V1, is maximal. We prove that this problem can be modeled as a linear program (with real variables) and therefore efficiently solved by standard algorithms. Then, we show how this result can be applied to model a land allocation problem by a 0–1 linear program. This problem consists in determining the cells of a land area, divided into a matrix of identical square cells, which must be harvested and the cells which must be left in old growth so that the weighted sum of the expected populations of some species is maximized. Some computational results are presented to illustrate the efficiency of the method. 相似文献
13.
Denis Cornaz 《Mathematical Programming》2006,105(2-3):329-344
Let G be a simple undirected graph with node set V(G) and edge set E(G). We call a subset independent if F is contained in the edge set of a complete multipartite (not necessarily induced) subgraph of G, F is dependent otherwise. In this paper we characterize the independents and the minimal dependents of G. We note that every minimal dependent of G has size two if and only if G is fan and prism-free. We give a 0-1 linear programming formulation of the following problem: find the maximum weight of
a complete multipartite subgraph of G, where G has nonnegative edge weights. This formulation may have an exponential number of constraints with respect to |V(G)| but we show that the continuous relaxation of this 0-1 program can be solved in polynomial time. 相似文献
14.
《Journal of Graph Theory》2018,88(4):551-557
We prove the titular statement. This settles a problem of Chvátal from 1973 and encompasses earlier results of Thomassen, who showed it for K3, and Collier and Schmeichel, who proved it for bipartite graphs. We also show that for every outerplanar graph there exists a planar hypohamiltonian graph containing it as an induced subgraph. 相似文献
15.
We deal with MAXH0-FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum solutions achieve approximation ratio (δ0+1)/(B+2+ν0), where B=maxv∈VdG(v), δ0=minv∈V(H0)dH0(v) and ν0=(|V(H0)|+1)/δ0. Next, we show that this ratio rises up to 3/(B+1) when H0=K3. Finally, we provide hardness results for MAXK3-FREE PARTIAL SUBGRAPH. 相似文献
16.
We consider a production planning problem for two items where the high quality item can substitute the demand for the low quality item. Given the number of periods, the demands, the production, inventory holding, setup and substitution costs, the problem is to find a minimum cost production and substitution plan. This problem generalizes the well-known uncapacitated lot-sizing problem. We study the projection of the feasible set onto the space of production and setup variables and derive a family of facet defining inequalities for the associated convex hull. We prove that these inequalities together with the trivial facet defining inequalities describe the convex hull of the projection if the number of periods is two. We present the results of a computational study and discuss the quality of the bounds given by the linear programming relaxation of the model strengthened with these facet defining inequalities for larger number of periods. 相似文献
17.
The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete
graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge
of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper
we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs.
Triangular elimination is a specific combination of zero-lifting and Fourier–Motzkin elimination using the triangle inequality.
We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof
is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities
of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing
inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.
相似文献
18.
Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs
下载免费PDF全文
![点击此处可从《Random Structures and Algorithms》网站下载免费的PDF全文](/ch/ext_images/free.gif)
In this paper we analyze the expected time complexity of the auction algorithm for the matching problem on random bipartite graphs. We first prove that if for every non‐maximum matching on graph G there exist an augmenting path with a length of at most 2l + 1 then the auction algorithm converges after N ? l iterations at most. Then, we prove that the expected time complexity of the auction algorithm for bipartite matching on random graphs with edge probability and c > 1 is w.h.p. This time complexity is equal to other augmenting path algorithms such as the HK algorithm. Furthermore, we show that the algorithm can be implemented on parallel machines with processors and shared memory with an expected time complexity of . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 384–395, 2016 相似文献
19.
Romeo Rizzi 《Discrete Mathematics》2009,309(12):4166-3600
We offer the following structural result: every triangle-free graph G of maximum degree 3 has 3 matchings which collectively cover at least of its edges, where γo(G) denotes the odd girth of G. In particular, every triangle-free graph G of maximum degree 3 has 3 matchings which cover at least 13/15 of its edges. The Petersen graph, where we can 3-edge-color at most 13 of its 15 edges, shows this to be tight. We can also cover at least 6/7 of the edges of any simple graph of maximum degree 3 by means of 3 matchings; again a tight bound.For a fixed value of a parameter k≥1, the Maximum k-Edge-Colorable Subgraph Problem asks to k-edge-color the most of the edges of a simple graph received in input. The problem is known to be APX-hard for all k≥2. However, approximation algorithms with approximation ratios tending to 1 as k goes to infinity are also known. At present, the best known performance ratios for the cases k=2 and k=3 were 5/6 and 4/5, respectively. Since the proofs of our structural result are algorithmic, we obtain an improved approximation algorithm for the case k=3, achieving approximation ratio of 6/7. Better bounds, and allowing also for parallel edges, are obtained for graphs of higher odd girth (e.g., a bound of 13/15 when the input multigraph is restricted to be triangle-free, and of 19/21 when C5’s are also banned). 相似文献
20.
Luidi Simonetti Alexandre Salles da Cunha Abilio Lucena 《Mathematical Programming》2013,142(1-2):511-538
Given an undirected graph $G$ with vertex and edge weights, the $k$ -cardinality tree problem asks for a minimum weight tree of $G$ containing exactly $k$ edges. In this paper we consider a directed graph reformulation of the problem and carry out a polyhedral investigation of the polytope defined by the convex hull of its feasible integral solutions. Three new families of valid inequalities are identified and two of them are proven to be facet implying for that polytope. Additionally, a Branch-and-cut algorithm that separates the new inequalities is implemented and computationally tested. The results obtained indicate that our algorithm outperforms its counterparts from the literature. Such a performance could be attributed, to a large extent, to the use of the new inequalities and also to some pre-processing tests introduced in this study. 相似文献