A simple 2-matching in an edge-weighted graph is a subgraph all of whose vertices have degree 1 or 2. We consider the problem of finding a maximum weight simple 2-matching that contains no triangles, which is closely related to a class of... more
A simple 2-matching in an edge-weighted graph is a subgraph all of whose vertices have degree 1 or 2. We consider the problem of finding a maximum weight simple 2-matching that contains no triangles, which is closely related to a class of relaxations of the TSP. Our main results are, for graphs with maximum degree 3, a complete description of
Research Interests:
Research Interests:
ABSTRACT The all-pairs min cut (APMC) problem on a normegative weighted graph is the problem of finding, for every pair of nodes, the min cut separating the pair. It is shown that on planar graphs, the APMC problem is equivalent to... more
ABSTRACT The all-pairs min cut (APMC) problem on a normegative weighted graph is the problem of finding, for every pair of nodes, the min cut separating the pair. It is shown that on planar graphs, the APMC problem is equivalent to another problem, the minimum cycle basis (MCB) problem, on the dual graph. This is shown by characterizing the structure of MCBs on planar graphs in several ways. This leads to a new algorithm for solving both of these problems on planar graphs. The complexity of this algorithm equals that of the best algorithm for either problem, but is simpler.
Research Interests:
Research Interests:
Research Interests:
... 7, Number 1 OPERATIONS RESEARCH LETFERS February 1988 RECOGNIZING MAXFLOW MINCUT PATH MATRICES * David B HARTVIGSEN Kellogg Graduate ... If an instance of (D) is a maximumflow prob lem on a matroid satisfying Seymour's characteri... more
... 7, Number 1 OPERATIONS RESEARCH LETFERS February 1988 RECOGNIZING MAXFLOW MINCUT PATH MATRICES * David B HARTVIGSEN Kellogg Graduate ... If an instance of (D) is a maximumflow prob lem on a matroid satisfying Seymour's characteri zation and if a ...
Research Interests:
ABSTRACT Gomory and Hu proved the following classical result: For any graph with nonnegative edge weights, there exists a collection of noncrossing cuts that contains a minimum cut for every pair of nodes. In this paper, we show how this... more
ABSTRACT Gomory and Hu proved the following classical result: For any graph with nonnegative edge weights, there exists a collection of noncrossing cuts that contains a minimum cut for every pair of nodes. In this paper, we show how this result generalizes for a natural multiterminal cut problem. We also show that our result is “best possible,” for k = 3, by using a computer to find feasible solutions to several large systems of linear inequalities. © 1999 John Wiley & Sons, Inc. Networks 34: 215–220, 1999