%A Govind P. Gupta %A Arjun Gupta %T Some Considerations on Interconnections of Computer Networks %R Technical Report CS-84-124 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X This technical report is a review of the considerations on Interconnection of Computer Networks. Fundamental concepts of Network architecture, implementation levels, routing and addressing are also reviewed. %Y cost: $2.60 %A Michael A. Langston %A Chul E. Kim %T Movement Coordination for Single-Track Robot Systems %R Technical Report CS-84-125 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X We consider problems associated with the coordination of movement within a multiple robot system in which all motion is restricted to a single track. Our objective is to minimize the reconfiguration time, that is, the total time required to move a collection of robots from an initial to a goal configuration. We show that various models give rise to a wide range of problem complexities. For these problems we design and analyze optimization and approximation strategies. %Y cost: $2.50 %A Jerzy Tiuryn %T An Introduction to First-Order Programming Logics %R Technical Report CS-84-126 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X The material included in this paper was presented during a course given at the Inter-University Center for Postgraduate Studies, Dubrovnik, Yugoslavia, January 15--30, 1983. Definitions of Algorithmic Logic, Dynamic Logic, and a simplification of the latter called a Logic of Programs are given, and these concepts are compared. The impact on the expressive power is discussed in the presence of: rich control, unbounded memory, and nondeterminism. %Y cost: $4.20 %A Keshav Sharma %T Syntactic Aspects of the Non-Deterministic Lambda Calculus %R Technical Report CS-84-127 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X Two kinds of non-deterministic lambda calculii are defined. The differentiation is made on the basis of the parameter passing mechanism, the call time choice mechanism defining the lambda C-calculus and the run time choice giving the lambda R-calculus. Convertibility relation is defined for both calculii. A new relation called the inclusion relation is also defined. Both calculii when restricted to deterministic terms give the ordinary lambda calculus. Then the notion of reduction for these calculii is developed. Specific reductions for the two calculii are introduced and proved to be Church-Rosser. The union of reductions for each calculus is also shown to be Church-Rosser. The consistency of the two theories lambda C and lambda R is also shown. Then some observations regarding further work are made. %Y cost: $7.20 %A Govind P. Gupta %A Gert v. Kortzfleisch %T Socio-Economic Consequences of Irrigation in Developing Countries -- A Systems Dynamics Study %R Technical Report CS-84-128 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X The paper presents a computer simulation model written in Dynamo and developed with System Dynamics techniques to study the complex agriculture system as a whole using data from the case studies of India. Some results are presented from the simulation providing insight of the intricacies of the system variables which may be used as guidelines before investing large funds in a project to optimize the benefits and to reduce the undesired consequences. The model can be used to study the effects of changes in one or more controllable variables in the overall effects on the performance of the system and the regional economy. It provides insights in the system variables which are responsible in making the planning a success. %Y cost: $3.10 %A Narsingh Deo %A M. S. Krishnamoorthy %A Michael A. Langston %T Exact and Approximate Solutions for the Gate Matrix Layout Problem %R Technical Report CS-85-129 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X We consider the gate matrix layout problem for VLS1 circuits, which is known to be NP-Complete. We present an efficient algorithm for determining whether two tracks suffice. For the general problem of minimizing the number of tracks (and hence the area) needed, we design an attractive dynamic programming formulation to guarantee optimality. We also investigate the performance of fast heuristic algorithms published in the literature and demonstrate that there exist families of problem instances for which the ratio of the number of tracks required by these heuristics to the optimal value is unbounded. Moreover, we show that this result holds for any on-line layout algorithm. We additionally prove that, unless P = NP, no polynomial-time layout algorithm can insure that the number of tracks it requires never exceeds r plus the optimum, for any constant r. %Y cost: $1.70 %A Jerzy Tiuryn %T A Simplified Proof of DDL < DL %R Technical Report CS-85-130 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X A simplified proof of the result stating that Deterministic Dynamic Logics is strictly weaker (with respect to expressive power) than Dynamic Logic of regular programs is given. This is a combinatorial proof, the main technical part of which may be of interest in its own. %Y cost: $1.50 %A Ravinder Krishnaswamy %A Chul E. Kim %T Digital Parallelism, Perpendicularity and Rectangle %R Technical Report CS-85-131 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X The slope of digital line segments is defined and an algorithm to evaluate it is presented. The parallelism and perpendicularity of two digital line segments are also defined. Finally, rectangular digital regions are defined and characterized and an algorithm is presented that determines whether or not a given digital region is a digital rectangle. %Y cost: $2.50 %A David B. Benson %T A Note on Partially-Ordered Semilattices %R Technical Report CS-85-132 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X A semilattice is a commutative idempotent semigroup. Equip this semigroup with a partial order such that the semigroup operation, +, is monotone in each argument separately. Then addition interpolates on intervals, x <= y implies x <= x + y <= y. The consequences generalize several aspects of powerdomain constructions. When the partially-ordered semilattices are equipped with a least element, bottom, and a unit, 0, for addition, the elements above zero have the Hoare lowerdomain structure and the elements below zero have the Smyth powerdomain structure. Some internal structure theory is briefly developed. We close by demonstrating the nonadmissibility of partially-ordered semilattices for CCS-type research. %Y cost: $1.00 %A Solveig A. Viste %A Chul E. Kim %T The Recognition of Digital Cylindrical Surfaces and Digital Moebius Strips %R Technical Report CS-85-133 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X Digital cylindrical surface and digital Moebius strip are defined. Algorithms to recognize each surface in digital three-space are developed which use properties local to each point in a given digital figure to determine properties of the entire figure. Given a set Q of digital points, the method employed determines from properties local to each point in the set whether Q forms a surface rather than a solid figure, and what the boundary of the set is if it does form a surface. If the boundary forms one (as in the case of the Moebius strip) or two (as for the cylindrical surface) closed curve(s), the surface is inspected to see if it has any kind of twist. The set of digital points is said to be a Moebius strip if it possesses a half-twist and a digital cylindrical surface if it has no twist at all. %Y cost: $3.50 %A Michael A. Langston %A Annette M. Morasch %T Interstage Transportation Planning in the Flow-Shop Environment %R Technical Report CS-85-134 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X In the well-known flow-shop model, we are given a k-stage processing facility and a collection of jobs, each comprising k tasks to be processed in order, one per stage. At every stage, one or more machines are available for performing tasks. We herein assume that the jobs are independent and that the processing of a task, once begun, cannot be interrupted. In this paper we focus our attention on a critical but largely ignored aspect of flow-shop utilization, namely, that of planning efficient transportation of work between stages. We therefore assume the existence of a transport, used to ferry jobs from one stage to the next. We devise and formally analyze effective transportation strategies for the static environment in which a single collection of jobs is available and we seek to process them all as quickly as possible. We also propose and empirically evaluate several transportation schemes for the dynamic environment in which a continuous job stream awaits processing and we seek instead to minimize the delay imposed by the transportation system. %Y cost: $3.70 %A Dilip Sarkar %A Narsingh Deo %T Estimating the Speedup in Parallel Parsing %R Technical Report CS-85-135 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %A Michael R. Fellows %A Michael A. Langston %T PROCESSOR UTILIZATION IN A LINEARLY CONNECTED PARALLEL PROCESSING SYSTEM %R Technical Report CS-85-140 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X We study the problem of assigning program fragments to a system of processing elements in which low-level operations are performed in parallel. Such a system, made realistic by the rapid advances in VLSI technology, is said to be linearly connected if each processing element can only communicate directly with its two nearest neighbors. We show that the problem of determining whether a perfect assignment exists is NP-complete, but can be solved in linear time if the numbers of processing elements is fixed. Furthermore, we demonstrate that the related problem of determining whether any assignment exists which can be performed in a given number of machine cycles is NP-complete. For this problem, whose objective corresponds to minimizing the program fragment's execution time, we also investigate the behavior of classes of near-optimal heuristic algorithms. We present evidence to indicate that guaranteeing acceptable worst-case performance is a very difficult problem as well. %A Michael R. Fellows %T ENCODING GRAPHS IN GRAPHS %R Technical Report CS-85-141 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X The subject of this dissertation is a theory of encodings of graphs in graphs. The following are some simple examples of problems to which the theory can be applied. .sp (1) Suppose a record is to be maintained of the current state from among a set of four possible states, between which any transition may occur. Suppose further that each update of the record, a binary vector of length 3 is to be accomplished by changing a single bit. (This problem is relevant to memory media presently on the horizon.) .sp (2) Suppose a parallel algorithm or program has its target architecture a synchronous network of four processors connected as the complete graph @K sub 4@ but is to be run on an architecture which has the connection topology of the cube @Q sub 3@. .sp In both problems, what we require (speaking intuitively for the moment) is an encoding of the complete graph @K sub 4@ in the cube @Q sub 3@. Note that a solution to problem (1) is not possible by encoding which assigns vectors 1:1 to states. A solution to problem (2) which is 1:1 incurs a relay cost'' of at least 2. %A Michael R. Fellows %T A CATEGORY OF GRAPHS FOR MULTIPROCESSING %R Technical Report CS-85-142 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X Two problems which arise in synchronous models of parallel processing with local memory and incomplete processor communication topology are considered from the standpoint of a category of encodings of graphs in graphs. The problems are: (a) the simulation of one multiprocessor by another (b) the scheduling of low-level parallel computations. The approach to the simulation problem presented here generalizes the notion of graph embedding (based on 1:1 correspondence of processes and processors) by allowing many:1 correspondences. A comparison is made with analogous results for the graph embedding model. It is shown that a trade-off is possible between functional redundancy and expansion cost. %A Michael R. Fellows %T A NOTE ON SUBDIVISIONS OF GRAPHS AND CYCLES MODULO K %R Technical Report CS-86-143 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X Several authors have considered the problem of determining conditions on a graph @G@ which insure the existence of cycles of length congruent to @d@ modulo @k@. In this note we prove a bound on minimum degree which insures that every subdivision of @G@ has a cycle of length divisible by @k@. %A Michael R. Fellows %T DATA STRUCTURES FOR RELUCTANT MEDIA %R Technical Report CS-86-144 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X The problem of maintaining data structures under restrictions on the number of bit changes per update is studied. By analogy with the problems posed by write-once memory media, bits are in the present problem written reluctantly. The problem is similarly motivated by memory media on the horizon. If state information is to be maintained, where the allowed state transitions are described by a graph @G@, then the problem is equivalent to a notion of encoding the graph @G@ in a graph derived from a cube. If @q(n)@ denotes the least @q@ such that the complete graph @K sub n@ can be encoded in @Q sub n@, then a major result can be stated @q(n) \sim n@. The results are obtained mainly by studying Cayley graphs. %A Bing-Chao Huang %A Michael A. Langston %T STABLE DUPLICATE-KEY EXTRACTION WITH OPTIMAL TIME AND SPACE BOUNDS %R Technical Report CS-86-145 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X We consider the problem of transforming a list @L@ of records sorted on some key into two sublists @L sub 1@ and @L sub 2@ where, for each distinct key in @L@, @L sub 1@ contains the first record of L which possesses the key and @L sub 2@ contains all records of @L@ with duplicate keys. We also desire that our duplicate-key extraction algorithm be stable (that is, records within each sublist must obey the original order given by @L@). This operation has fundamental applications in data base and related file processing environments whenever a collection of distinct keys need only be considered. Moreover, stability in extraction insures that @L@ can be efficiently restored at a later time with a stable merge of @L sub 1@ and @L sub 2@. Any procedure for performing duplicate-key extraction on a file of size @n@ must require at least @O(n)@ time and @O(1)@ extra space, although the obvious algorithms for achieving either bound alone violate the other. We design a stable algorithm, using block-rearrangement techniques, and prove that it is optimal in the theoretical sense that it achieves both lower bounds simultaneously. We also show that its worst-case number of key comparisons and record exchanges sum to no more than @6n@, suggesting that the algorithm has practical application as well. %A Sajal K. Das %A Narsingh Deo %T STIRLING GRAPHS AND THEIR PROPERTIES %R Technical Report CS-86-146 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X We define a new family of adjacency matrices, called the Stirling matrices, and study the corresponding family of simple connected graphs, called the Stirling graphs. We explore various connectivity properties of these graphs from the viewpoint of their potential for interconnection networks in multiprocessing systems. Every Stirling graph of order three or more has a Hamiltonian cycle as well as a complete binary tree in which all vertices at each level are connected with a cycle. The diameter of the Stirling graph of order @n@ is @lceil log su 2 (n+1) rceil -1@, and the number of edges has an upper bound of @0(n sup {1.59})@. Stirling graphs compare favorably with leaf-ringed binary tree networks. %A M. Kathryn Di Benigno %A George R. Cross %A Gary G. deBessonet %T COREL - A CONCEPTUAL RETRIEVAL SYSTEM %R Technical Report CS-86-147 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X Corel is an experimental retrieval system that employs techniques of artificial intelligence. Articles of the Civil Code of Louisiana have been conceptually indexed using frame-based knowledge structures in hope of improving accessibility over traditional key-word retrieval systems. A set of macro packages has been developed to allow a domain expert to implement a retrieval system based on this methodology. %A David B. Benson %T THE SECOND LABOR OF HERCULES: AN ESSAY ON SOFTWARE ENGINEERING AND THE STRATEGIC DEFENSE INITIATIVE %R Technical Report CS-86-148 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X Building computer programs is called software engineering. Software engineering is an engineering discipline which is in its infancy. Engineering of all kinds builds on experience. Software engineering has little experience. Software engineers cannot build large software which works the first time, let alone the much more difficult task of engineering battle software which works the first time. .sp 1 The envisaged Strategic Defense Initiative ballistic missile defense would require the largest battle software ever thought about. It must work the first time. .sp 1 The essay describes traditional engineering practice and software engineering practice without technical terms. The meaning of trustworthy software is defined and the state of the art in establishing trust in software is described. The special aspects of military software are reviewed. All of this is applied to the Strategic Defense Initiative software. A practical means to establish confidence in battle software is described. .sp 1 The essay is summarized in a recapitulation section. The conclusions of the essay suggest actions which the U.S. government should take. .sp 1 An extensive bibliography on software engineering and the Strategic Defense Initiative is included. %A Mohammed Nasiruddin %A George R. Cross %A Cary G. deBessonet %T THE STRUCTURE OF CCLIPS %R Technical Report CS-86-149 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X The Civil Code Legal Information Processing System (CCLIPS) is a conceptual retrieval system whose domain is the Louisiana Civil Code. Statutes are coded in Atomically Normalized Form (ANF) and entered into a database. Legal situations are entered by the user in ANF and relevant statutes are retrieved. We discuss the current status of the system and some plans for further development. %A Bing-Chao Huang %A Michael A. Langston %T PRACTICAL IN-PLACE MERGING %R Technical Report CS-86-150 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X We present a novel, yet straightforward linear-time algorithm for merging two sorted lists in a fixed amount of additional space. Constant of proportionality estimates and empirical testing reveal that this procedure is reasonably competitive with merge routines free to squander unbounded additional memory, making it particularly attractive for applications such as the external merge-sorting of very large files. %A David B. Benson %T COMMUNICATING COAUTOMATA %R Technical Report CS-86-151 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X Communicating coautomata live in powerdomains, which we view as @k@-modules. We begin by showing that incompletely specified nondeterministic state machines (automata) are a particular form of @A@-module over a semigroup @k@-algebra @A@, where @k@ is the commutative unital semiring B = {0,1} with inclusive or'' as addition and and'' as multiplication. Then we can equally well consider output machines (coautomata) which, without input, change state and output some symbol. The coautomata view provides a lovely way to think about communication between processes,'' a proper communication being required before each process'' can continue. For simplicity we consider only the synchronous case. .sp 1 The algebra all works quite nicely, providing a sound (re)-formulation of many researcher's view of communicating processes'' in elegant mathematical terms. At the end I pose so-called safety and liveness questions which suitable topologies may aid in answering. %A David B. Benson %A Jerzy Tiuryn %T FIXED POINTS IN FREE PROCESS ALGEBRAS WITH SILENT EVENTS, PART I %R Technical Report CS-86-152 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X Characterizing and finding fixed point solutions to equations in free process algebras is accomplished by first considering the structure of the free process algebras and then applying a particular proof technique developed for the purpose. The fixed point solutions for systems of equations for a class of polynomials is important in applications, the linear left simple polynomials, are characterized and explicitly given. The second part of this paper will apply the proof methods to characterizing and giving solutions to equations for other classes of polynomials over free process algebras. %A David B. Benson %T STRING ALGEBRAS AND COALGEBRAS, AUTOMATA AND COAUTOMATA %R Technical Report CS-86-153 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X The concatenation algebra of strings has a dual, the coalgebra of decomposing strings into prefixes and suffixes. The decomposition coalgebra has been implicitly used in defining the run map of automata and related concepts. This paper makes the role of decomposition explicit. Dual to automata which read input strings are the coautomata which write output strings. The coautomata require the decomposition coalgebra to define the run map with and from the concatenation algebra. .sp 1 We give a careful definition of the run maps for automata and coautomata, proving that the run maps for nondeterministic incompletely-specified outputless automata have (semiring) module structure while the run maps for nondeterministic incompletely-specified inputless coautomata have (semiring) comodule structure. The two proofs are not exact duals of one another. %A Dilip Sarkar %T LESSA: AN ARRAY TO SOLVE A SET OF LINEAR EQUATIONS %R Technical Report CS-86-154 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X A dedicated linear array of simple processors is proposed to solve a set of linear equations. Data structure and algorithm also presented for the array to solve a set of @n@ linear equations in @O(n sup 2+3.n )@ time on an array of @n@ processors. The given algorithm is a parallelization of the Gaussian elimination algorithm. The data input to the array is purely sequential. The algorithm is optimal, within a constant, in its time and area requirements. %A Donald K. Friesen %A Michael A. Langston %T BIN PACKING: ON OPTIMIZING THE NUMBER OF PIECES PACKED %R Technical Report CS-86-155 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X We consider bin-packing variations related to the well-studied problem of maximizing the total number of pieces packed into a fixed set of bins. We show that, when the objective is to minimize the total number of pieces packed subject to the constraint that no unpacked piece will fit, no polynomial-time relative approximation exists (unless, of course, @P=NP@). That is, we prove that it is NP-hard to guarantee packing no more than a constant multiple of the optimal number of pieces, for any constant. This appears to be the first bin-packing problem for which this property has been demonstrated. Furthermore, this result also holds for the allied packing variant which seeks to minimize the maximum number of pieces packed in any single bin. We find the situation to be markedly better for the problem of maximizing the minimum number of pieces in any bin. If all bins possess the same capacity, we prove that the familiar SPF rule is an absolute approximation algorithm with additive constant 1, and can therefore be regarded as a best possible heuristic. For the more general and difficult case in which bin capacities may differ, it turns out that SPF fails to qualify as even a relative approximation algorithm. However, we devise an implementation of the well-known FFD heuristic, which we show to be a relative approximation algorithm, yielding a worst-case performance ratio of 1/2 with additive constant 0. Moreover, we prove that (unless @P=NP@) no polynomial-time algorithm can guarantee a higher ratio without sacrificing the additive constant. %A Vijay Aggarwal %A Narsingh Deo %A Dilip Sarkar %T THE KNAPSACK PROBLEM WITH DISJOINT MULTIPLE CHOICE CONSTRAINTS %R Technical Report CS-86-156 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X This paper considers the binary knapsack problem under disjoint multiple-choice constraints. It proposes a two-stage algorithm based on Lagrangean relaxation. The first stage in polynomial effort determines the optimal Lagrange multiplier value, which is then used in a branch and bound scheme to rank-order the choice-sets, and thus obtain an optimal solution in a relatively low depth of search. The validity of the algorithm is established, a numerical example is included, and advantages over other schemes are outlined. %A C. E. Kim %T MINIMUM LENGTH PREIMAGE OF DIGITAL ARCS %R Technical Report CS-86-157 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X The lengths of the preimages of digital arcs are considered. In the case of digital line segments we find the preimages of the maximum and minimum length preimages and proposes an approximate average of the two as an estimator of digital line segments. In the case of digital arcs in general, a linear time algorithm is presented that computes the minimum length preimage, which may be used as a first approximation length of digital arcs. %A C. E. Kim %A R. Krishnaswamy %T CONGRUENT CONVEX DIGITAL REGIONS UNDER TRANSLATION %R Technical Report CS-86-158 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X The congruency of two convex digital regions under translation is defined and its properties are discussed. An @O(m+n sup 3logn )@ time algorithm is presented that determines whether or not two convex digital regions are congruent under translation. %A R. Krishnaswamy %A C. E. Kim %T PROBLEMS OF POSTING SENTRIES %R Technical Report CS-86-159 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X We consider the problem of posting a minimum number of sentries to watch every point on the boundary of convex polygons enclosed in a polygon. A linear time algorithm is presented to obtain an optimal posting for a polygon in a nonconvex polygon. It is shown that the problem for a nonconvex polygon in a convex enclosure is NP-hard and so is the problem for a set of convex polygons in a convex enclosure. An exhaustive algorithm to compute an optimal posting for two convex polygons in a convex enclosure is also presented. %A Michael R. Fellows %A Donald K. Friesen %A Michael A. Langston %T ON FINDING OPTIMAL AND NEAR-OPTIMAL LINEAL SPANNING TREES %R Technical Report CS-86-160 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X The search for good lineal, or depth-first, spanning trees is an important aspect in the implementation of a wide assortment of graph algorithms. We consider the complexity of finding optimal lineal spanning trees under various notions of optimality. In particular, we show that several natural problems, such as constructing a shortest or a tallest lineal tree, are NP-complete. We also address the issue of polynomial-time, near-optimization strategies for these difficult problems, showing, among other things, that efficient absolute approximation algorithms cannot exist unless @P=NP@. %A Alan Genz %T THE NUMERICAL EVALUATION OF MULTIPLE INTEGRALS ON PARALLEL COMPUTERS %R Technical Report CS-86-161 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X The problem of efficient implementation of numerical integration algorithms on parallel computers is considered. First, a general discussion of both adaptive and nonadaptive algorithms, including possible differences in implementation for vector machines, SIMD machines and MIMD machines is given. The implementation of a globally adaptive algorithm on three different parallel computers is discussed, and test results are reported. %A Michael R. Fellows %A Michael A. Langston %T THE END OF INNOCENCE IN POLYNOMIAL-TIME COMPLEXITY %R Technical Report CS-86-162 %I Computer Science Department, Washington State University %C Pullman, WA 99164-1210 %X The field of computational complexity for concrete, practical combinatorial problems has developed in a remarkably smooth fashion. One can point to several features of the theory of polynomial-time computability which make it especially well-behaved, including: .sp 1 1. the modelling of feasible computing by polynomial-time complexity is well-supported by the fact that almost all known polynomial-time algorithms for natural problems have running times bounded by of low order polynomials .sp 1 2. problems are invariably known to be decidable in polynomial-time by direct evidence in the form of efficient algorithms .sp 1 3. while the theory is formulated in terms of decision problems, almost all known algorithms proceed by actually constructing a solution to the problem at hand. .sp 1 Recent advances in graph theory and graph algorithms dramatically alter this situation on all three counts. Powerful and easy-to-apply tools are now available for classifying problems as decidable in polynomial time by non-constructively proving only the existence of polynomial-time decision algorithms. These tools neither specify the degree of the polynomial, produce the decision algorithm, nor guarantee that such an algorithm is of any use in constructing a solution. These developments present both practitioners and theorists with novel challenges.