10770582
Polynomial and abstract subrecursive classes
We define polynomial time computable operator. Our definition generalizes Cook's definition to arbitrary function inputs. Polynomial classes are defined in terms of these operators; the properties of these classes are investigated. Honest polynomial classes are generated by running time. They posses a modified Ritchie-Cobham property. A polynomial class is a complexity class iff it is honest.
 Starting from the observation that many results about subrecursive classes hold for all reducibility relations (e.g. primitive recursive in, elementary recursive in), which were studied so far, we define abstract subrecursive reducibility relation. Many results hold for all abstract subrecursive reducibilities.
47385179
Matching Algorithms Are Fast in Sparse Random Graphs
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every non-maximum matching has an augmenting path of length O(log n). This implies that augmenting path algorithms like the Hopcroft–Karp algorithm for bipartite graphs and the Micali–Vazirani algorithm for general graphs, which have a worst case running time of \(O(m\sqrt{n})\), run in time O(m log n) with high probability, where m is the number of edges in the graph. Motwani proved these results for random graphs when the average degree is at least ln(n) [Average Case Analysis of Algorithms for Matchings and Related Problems, Journal of the ACM, 41(6), 1994]. Our results hold, if only the average degree is a large enough constant. At the same time we simplify the analysis of Motwani.
5720611
A Correctness Certificate for the Stoer-Wagner Min-Cut Algorithm
The Stoer‐Wagner algorithm computes a minimum cut in a weighted undirected graph. The algorithm works inn 1 phases, wheren is the number of nodes ofG. Each phase takes time O.mCn logn/ ,w herem is the number of edges ofG, and computes a pair of vertices s and t and a minimum cut separatings and t . We show how to extend the algorithm such that each phase also computes a maximum flow from s tot . The flow is computed in O.m/ additional time and certifies the cut computed in the phase. © 1999 Elsevier Science B.V. All rights reserved. We give a correctness certificate for the min-cut algorithm of Stoer and Wagner [6]. This algorithm refines the algorithm of Nagamochi and Ibaraki [5,4]; it has the same time complexity, but is simpler. The algorithm is deterministic. There are faster randomized algorithms [2,3]. No certificates are known for the randomized algorithms. Let G be an undirected graph with n vertices and m edges. The algorithm of Stoer and Wagner works inn 1 phases. In each phase it identifies two vertices and a minimum cut separating them and then collapses the two vertices into one. The global min-cut is the minimum cut found in any phase. Each phase runs in time O.mCn logn/. We extend the algorithm such that it also finds a flow equal to the min-cut in each phase. The additional time required to find the flow is O.m/ in each phase.
47415035
Polynomial and Abstract Subrecursive Classes
The reducibility ''polynomial time computable in'' for arbitrary functions isintroduced. It generalizes Cook's definition from sets to arbitrary functions. A complexity-theoretic as well as a syntactic characterization is given and their equivalence is shown. This equivalence and the naturalness of both definitions give evidence that our notion is ''correct.'' The computable functions are classified into polynomial classes according to this reducibility. The ordering of these classes under set inclusion is studied. Honest classes are introduced and using them, the classification is related to the computational complexity of the functions classified. The algebraic structure of honest classes is also investigated. In Section II abstract subrecursive reducibilities are introduced. An axiomaticdefinition in purely recursion-theoretic terms is given; in particular, no reference to a particular machine model is needed. The definition is in the spirit of Strong's and Wagner's characterizations of basic recursive function theories. All known reducibilities are abstract reducibilities. The algebraic structure of abstract classes is explored.
41059566
On local routing of two-terminal nets
Abstract We examine the problem of finding edge-disjoint paths between pairs of vertices placed on inner as well as outer faces of a finite grid graph. For each path a global routing, which fixes the topology of the path relative to the nontrivial faces, is part of the input. We give necessary and sufficient conditions for the solvability of the problem and provide an algorithm to find a solution with running time quadratic in the size of the problem.
47033631
Rank-maximal matchings
Suppose that each member of a set <i>A</i> of applicants ranks a subset of a set <i>P</i> of posts in an order of preference, possibly involving ties. A <i>matching</i> is a set of (applicant, post) pairs such that each applicant and each post appears in at most one pair. A <i>greedy</i> matching is one in which the maximum possible number of applicants are matched to their first choice post, and subject to that condition, the maximum possible number are matched to their second choice post, and so on. This is a relevant concept in any practical matching situation and it was first studied by Irving [8].We define the bipartite graph <i>G</i> = (<i>A U P,ε</i>), where ε consists of all pairs (<i>a, p</i>) such that post <i>p</i> appears in the preference list of applicant <i>a.</i> Each edge (<i>a, p</i>) has a rank <i>i</i>, which means that post <i>p</i> is an <i>i</i>th choice for applicant <i>a.</i> The traditional solution of computing a greedy matching in <i>G</i> would be to use the Hungarian algorithm to compute a maximum weight matching by assigning a suitably steeply decreasing sequence of weights to the edges. This would result in an algorithm with worst case running time <i>rn</i>(<i>m</i> + <i>n</i> log <i>n</i>) and the space requirement Θ(<i>rm</i>), where <i>n</i> is the number of vertices, <i>m</i> is the number of edges and <i>r</i> is the largest rank of an edge.Here, we describe two algorithms to compute a greedy matching that improve upon this algorithm. We give a combinatorial algorithm with running time <i>O</i>(min(<i>n</i> + <i>C,C</i>√<i>n</i>)<i>m</i>), where <i>C</i> ≤ <i>r</i> is the maximal rank of an edge used in a greedy matching. This algorithm works in phases and uses the maximum cardinality matching algorithm. We also give an <i>O</i>(<i>Cnm</i>) algorithm that tackles the problem of large edge weights introduced by the Hungarian algorithm. This algorithm uses scaling and works in phases. The space requirement of both these algorithms is <i>O</i>(<i>m</i>).
2560175
LEDA: a platform for combinatorial and geometric computing
Combinatorial and geometric computing is a core area of computer science (CS). In fact, most CS curricula contain a course in data structures and algorithms. The area deals with objects such as graphs, sequences, dictionaries, trees, shortest paths, flows, matchings, points, segments, lines, convex hulls, and Voronoi diagrams and forms the basis for application areas such as discrete optimization, scheduling, traffic control, CAD, and graphics. There is no standard library of the data structures and algorithms of combinatorial and geometric computing. This is in sharp contrast to many other areas of computing. There are, for example, packages in statistics (SPSS), numerical analysis (LINPACK, EISPACK), symbolic computation (MAPLE, MATHEMATICA), and linear programming (CPLEX).
6531885
TSP-based curve reconstruction in polynomial time
An instance of the curve reconstruction problem is a finite sample set V of an unknown curve V and the task is to connect the points in V in the order in which they lie on % Giesen [Gie99] showed recently tha t the Traveling Salesman tour of V solves the reconstruction problem under fairly week assumptions on V and V. We extend his result along three dimensions. We weaken the assumptions, we give an al ternate proof, and we show tha t in the context of curve reconstruction the Traveling Salesman tour can be constructed in polynomial time. 1 I n t r o d u c t i o n An instance of the curve reconstruction problem is a finite sample set V of an unknown curve -)' and the task is to construct a graph G on V such that two points in V are connected by an edge of G iff the points are adjacent on % The graph G is called a polygonal reconstruction of 7The curve reconstruction problem and the related surface reconstruction problem received a lot of at tention in the graphics and the computat ional geometry community. We are interested in reconstruction algorithms with guaranteed per/ormanc¢, i.e., a lgori thms which provably solve the reconstruction problem under certain assumptions on ~/ and V. Figure 1 i l lustrates the curve reconstruction problem. If the curve is closed, smooth, and uniformly sampled, several methods are known to work ranging over minimum spanning trees [FG94], a shapes [BB97, EKS83], B-skeletons [KR85], and r-regular shapes [Att97]. A survey of these techniques appears in [Ede98]. The case of non-uniformly sampled closed curves was first t reated successfully by Amenta, Bern and Eppstein [ABE98] and subsequently improved algorithms such as [DK99, Go199] appeared. Open nonuniformly sampled curves were treated in [DMR99]. All papers mentioned so far require that the underlying ~ a x c h partially supported by EG-projects ALCOM-IT and GALIA. tMax-Planck-Institute fiir Inforrnatik, Irn Stadtwald, 66123 Saarbr/icken $Max-Planck-Institute fiir Informatik, Irn Stadtwald, 66123 Saarbriicken . . 1. . ._.
17694660
Resource Constrained Shortest Paths
The resource constrained shortest path problem (CSP) asks for the computation of a least cost path obeying a set of resource constraints. The problem is NP-complete. We give theoretical and experimental results for CSP. In the theoretical part we present the hull approach, a combinatorial algorithm for solving a linear programming relaxation and prove that it runs in polynomial time in the case of one resource. In the experimental part we compare the hull approach to previous methods for solving the LP relaxation and give an exact algorithm based on the hull approach. We also compare our exact algorithm to previous exact algorithms and approximation algorithms for the problem.
9207249
Traveling Salesman-Based Curve Reconstruction in Polynomial Time
An instance of the curve reconstruction problem is a finite sample set V of an unknown collection of curves $\gamma$. The task is to connect the points in V in the order in which they lie on $\gamma$. Giesen [Proceedings of the 15th Annual ACM Symposium on Computational Geometry (SCG '99), 1999, pp. 207--216] showed recently that the traveling salesman tour of V solves the reconstruction problem for single closed curves under otherwise weak assumptions on $\gamma$ and V; $\gamma$ must be a single closed curve. We extend his result along several directions: 
we weaken the assumptions on the sample; we show that traveling salesman-based reconstruction also works for single open curves (with and without specified endpoints) and for collections of closed curves; we give alternative proofs; and we show that in the context of curve reconstruction, the traveling salesman tour can be constructed in polynomial time.
12636571
Curve reconstruction: connecting dots with good reason
Curve reconstruction algorithms are supposed to reconstruct curves from point samples. Recent papers present algorithms that come with a guarantee: Given a sufficiently dense sample of a closed smooth curve, the algorithms construct the correct polygonal reconstruction. Nothing is claimed about the output of the algorithms, if the input is not a dense sample of a closed smooth curve, e.g., a sample of a curve with endpoints. We present an algorithm that comes with a guarantee for any setP of input points. The algorithm constructs a polygonal reconstruction G and a smooth curve that justifies G as the reconstruction fromP . © 2000 Elsevier Science B.V. All rights reserved.