1,721,231 research outputs found
A note on range-restricted circuit covers
Full text linkLet Cone(G), Int.Cone(G) and Lat(G) be the cone, the integer cone and the lattice of the incidence vectors of the circuits of graph G. A good range is a set K of natural numbers such that the intersection of Cone(G), Lat(G) and K^E is contained in Int.Cone(G) for every graph G=(V,E). We give a counterexample to a conjecture of Goddyn [ Goddyn, L.A.: Cones, Lattices and Hilbert Bases of Circuits and Perfect Matchings. Contemporary Mathematics 147, 419--439 (1993)] stating that N\{1} is a good range
A Simple Minimum T-Cut Algorithm
No full textWe give a simple algorithm for finding a minimum T-cut. At present, all known efficient algorithms for this problem go through the computation of a Gomory-Hu tree. While our algorithm bases on the same fundamental properties of uncrossing as the previous methods, still it provides an ad-hoc solution. This solution is easier to implement and faster to run. Our results extend to the whole of symmetric submodular functions
Impaccando T-tagli e T-giunti
No full textquesto articolo era inteso a presentare a grandi linee i contenuti ed i contributi principali dellla tesi di Dottorato di Romeo Rizzi alla comunita' dei matematici italiana
Konig's Edge Coloring Theorem without augmenting paths
No full textWe give a simple, self-contained proof of the following
basic fact in matching theory:
Every bipartite regular multigraph is factorizable.
Our proof does not use any alternating path argument
Review for the AMS: MR2393045 The complexity of recognizing linear systems with certain integrality properties
No full textAcyclically pushable bipartite permutation digraphs: An algorithm
No full textAbstractGiven a digraph D=(V,A) and an X⊆V, DX denotes the digraph obtained from D by reversing those arcs with exactly one end in X. A digraph D is called acyclically pushable when there exists an X⊆V such that DX is acyclic. Huang, MacGillivray and Yeo have recently characterized, in terms of two excluded induced subgraphs on 7 and 8 nodes, those bipartite permutation digraphs which are acyclically pushable. We give an algorithmic proof of their result. Our proof delivers an O(m2) time algorithm to decide whether a bipartite permutation digraph is acyclically pushable and, if yes, to find a set X such that DX is acyclic. (Huang, MacGillivray and Yeo's result clearly implies an O(n8) time algorithm to decide but the polynomiality of constructing X was still open.)We define a strongly acyclic digraph as a digraph D such that DX is acyclic for every X. We show how a result of Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1–3) (1999) 27–33] can be essentially regarded as a characterization of strongly acyclic digraphs and also provides linear time algorithms to find a strongly acyclic orientation of an undirected graph, if one exists. Besides revealing this connection, we add simplicity to the structural and algorithmic results first given in Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1–3) (1999) 27–33]. In particular, we avoid decomposing the graph into triconnected components.We give an alternate proof of a theorem of Huang, MacGillivray and Wood characterizing acyclically pushable bipartite tournaments. Our proof leads to a linear time algorithm which, given a bipartite tournament as input, either returns a set X such that DX is acyclic or a proof that D is not acyclically pushable
Excluding a Simple Good Pair Approach to Directed Cuts
No full textIn 1972, Mader proved that every undirected graph has a good pair, that is, an ordered pair (u,v) of nodes such that the star of v is a minimum cut separating u and v. In 1992, Nagamochi and Ibaraki gave a simple procedure to find a good pair as the basis of an elegant and very efficient algorithm to find minimum cuts in graphs. This paper rules out the simple good pair approach for the problem of finding a minimum directed cut in a digraph and for the more general problem of minimizing submodular functions. In fact, we construct a digraph with no good pair. Note that if a graph has no good pair, then it may not possess a so-called cut-equivalent tree. Benczu'r constructed a digraph with no cut-equivalent tree; our counterexample thus extends Benczu'r's one
On Rajagopalan and Vazirani's 3/2-Approximation Bound for the Iterated 1-Steiner Heuristic
No full textLet G=(V,E) be an undirected graph with costs on the edges specified
by a weighting w of the edges by positive reals.
A Steiner tree is any tree of G which spans all nodes in a given subset R of V.
When V / R is a stable set of G, then (G,R) is called quasi-bipartite.
Rajagopalan and Vazirani introduced the notion of quasi-bipartiteness
and showed that the Iterated 1-Steiner heuristic
always produces a Steiner tree of total cost at most 3/2 the optimal
when (G,R) is quasi-bipartite and w is a metric.
In this paper,
we give a more direct and much simpler proof of this result.
Next, we show how a bit scaling approach yields
a polynomial time implementation of the Iterated 1-Steiner heuristic.
This gives a 3/2-approximation algorithm
for the problem considered by Rajagopalan and Vazirani
Indecomposable r-graphs and some other counterexamples
Full text linkAn r-graph is any graph that can be obtained as a conic combination of its own 1-factors. An r-graph G=(V,E) is said indecomposable when its edge set E cannot be partitioned as the disjoint union of sets E_1 and E_2 so that (V,E_i) is an r_i-graph for i=1,2 and for some r_1, r_2. We give an indecomposable r-graph for every integer r >= 4. This answers a question raised in 1: [ P.D. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proceedings of the London Mathematical Society, Vol. 38, 423--460, (1979)] and 2: [ P.D. Seymour, Some unsolved problems on one-factorizations of graphs. Graph Theory and Related Topics, J.A. Bondy and U.S.R. Murty, Eds., 367--368, Academic Press, New York, 1979] and has interesting consequences for the Schrijver System of the T-cut polyhedron to be given in 3: [ R. Rizzi, Minimum T-cuts and optimal T-pairings, Discrete Mathematics, 2002]. A graph in which every two 1-factors intersect is said to be poorly matchable. Every poorly matchable r-graph is indecomposable. We show that for every r >= 4 "being indecomposable" does not imply "being poorly matchable". Next we give a poorly matchable r-graph for every r >= 4. The paper provides counterexamples to some conjectures of Seymour first appeared in [1] and [2]
On 4-connected graphs without even cycle decompositions
No full textAbstractA circuit decomposition of a graph G=(V,E) is a partition of E into circuits. A decomposition is said even if all its circuits have even length. We give a negative answer to a question posed by Jackson asking whether K5 is the only 4-connected eulerian graph with an even number of edges but no even circuit decomposition
- …
