Abstract The p‐median problem for networks is NP‐hard, but polynomial time algorithms exist for trees (n is the number of nodes): O(pn2) by Tamir, and O(n lgp + 2 n) by Benkoczi and Bhattacharya. Goldman gave an O(n) algorithm for the 1‐median problem on trees. Mirchandani and Oudjit proved localization properties for 2‐medians on trees; these were later used to obtain an O(nlg n) bound, and, in special cases, O(n) . We present a framework that unifies all efficient algorithms for the 2‐median problem on trees. Our framework isolates the nonlinear part of the computation so that future time‐bound improvements are easily incorporated. We also introduce a method for reducing the search space, improving all known runtimes in many instances. Finally, we give a new algorithm for the case where edge lengths are positive integers. The associated time bound is O(n + D) , where D is the sum of the logarithms of edge lengths. This is O(n) if edge lengths are bounded by a constant and O(n lglg n) if they are O(lg n) . The algorithm is flexible enough to extend to noninteger edge lengths, preserving the time bound in some circumstances.

Our goal in creating the Graph SKetching tool, GSK, was to provide blind screen reader users with a means to create and access graphs as node-link diagrams and share them with sighted people in real-time. Through this effort, we hoped to better include blind people in computing and other STEM disciplines in which graphs are important. GSK proved very effective for one blind computer science student in courses that involved graphs and graph structures such as automata, decision trees, and resource-allocation diagrams. In order to determine how well GSK works for other blind people, we carried out a user study with ten blind participants. We report on the results of the user study, which demonstrates the efficacy of GSK for the examination, navigation, and creation of graphs by blind users. Based on the study results, we improved the efficiency of GSK for blind users. We plan more enhancements to help meet the need for accessible graph tools as articulated by the blind community.

While the improvement of computer science students' communication skills has frequently been called for in the literature, employers continue to feel that recent graduates are not equipped with the writing, speaking, and teaming skills essential in the 21st century workplace. One problem with previous approaches is that they often teach communication skills in dedicated courses rather than integrating them into technical classes across the curriculum. In this paper, we report on a multi-institutional faculty team's efforts to integrate communication skills into mid-level data structures and algorithms courses as part of a larger NSF-funded project to enact integrated reform throughout computer science/software engineering curricula. We present an outline of assignments designed to develop communication skills (writing, speaking, reading, listening, and teaming) intertwined with technical skills, and discuss our preliminary efforts to assess these efforts. Our work reflects a general approach to incorporate communication activities within the computer science curricula and to help students learn and communicate technical content in academic and professional settings.

Combinatorial graphs, often conveyed as node-link diagrams, figure prominently in Computer Science and other Science, Technology, Engineering, and Mathematics (STEM) disciplines. Unfortunately, they are most often inaccessible to blind students and professionals. This paper introduces GSK, a self-contained Graph SKetching tool that allows blind and sighted people to easily create, edit, and share graphs in real-time using interaction mechanisms (mouse, keyboard, monitor, screen reader) that are standard for them. GSK was successfully used by a blind Computer Science student and his sighted instructors to create and access graphs specific to his automata theory and operating systems courses. Our hope is that GSK will enable more blind STEM students and professionals to actively participate in their disciplines by providing them and their sighted colleagues with a cross-collaboration tool that allows them to share graphs just as easily as they share text and word processing documents.

Selecting and precomputing indexes and materialized views, with the goal of improving query-processing performance, is an important part of database-performance tuning. The significant complexity of the view- and index-selection problem may result in high total cost of ownership for database systems. In this paper, we develop efficient methods that deliver user-specified quality of the set of selected views and indexes when given view- and index-based plans as problem inputs. Here, quality means proximity to the globally optimum performance for the input query workload given the input query plans. Our experimental results and comparisons on synthetic and benchmark instances demonstrate the competitiveness of our approach and show that it provides a winning combination with end-to-end view- and index-selection frameworks such as those of [1, 2].

In on-line analytical processing (OLAP), precomputing (materializing as views) and indexing auxiliary data aggregations is a common way of reducing query-evaluation time costs for important data-analysis queries. We consider an OLAP view- and index-selection problem stated as an optimization problem, where (i) the inputs include the data-warehouse schema, a set of data-analysis queries of interest, and a storage-limit constraint, and (ii) the output is a set of views and indexes that minimizes the costs of the input queries, subject to the storage limit. While greedy and other heuristic strategies for choosing views or indexes might help to some extent in improving the costs, it is highly nontrivial to arrive at a globally optimum solution, one that reduces the processing costs of typical OLAP queries as much as is theoretically possible. In fact, as observed in [17] and to the best of our knowledge, there is no known approximation algorithm for OLAP view or index selection with nontrivial performance guarantees.

ProofChecker is a graphical program based on the notion of formal correctness proofs that allows students, both sighted and visually impaired, to draw a deterministic finite automaton (DFA) and determine whether or not it correctly recognizes a given language. Sighted students use the mouse and graphical controls to draw and manipulate the DFA. Keyboard shortcuts, together with the use of a screen reader to voice the accessible descriptions provided by the program, allow visually impaired students to do the same.

Prompted by changes in the numbers and demographics of students enrolled and being retained in computer science, the Department of Computer Science at NC State University is revising its undergraduate curriculum to better meet the needs of its students, and increase student attraction and retention. One set of changes concerns introductory computer science courses (CS1). This paper reports on a study conducted to assess the impact of class size and active learning in our CS1 courses. We find that smaller classes with integrated laboratories improve both learning and retention, as well as satisfaction of the students. Among other benefits, we found retention rates in small classes to be about 20% better than large classes.

Covering problems arise in many areas of electronic design automation such as logic minimization and technology mapping. An exact solution can critically impact both size and performance of the devices being designed. This paper introduces eclipse, a branch-and-bound solver that can solve many covering problems orders of magnitude faster than existing solvers. When used in place of the default covering engine of a well-known logic minimizer, eclipse makes it possible to find, in less than six minutes, true minima for three benchmark problems that have eluded exact solutions for more than a decade.

When an activity-on-arc (AoA) project network is to be constructed, one typically seeks to minimize the number of dummy arcs. Recent investigations have shown, however, that the computational effort of many network-oriented project management techniques depends strongly on the so-called complexity index (CI) of a network. We show other justifications for minimizing the CI rather than the number of dummy arcs. We also present a polynomial time algorithm for constructing an AoA network with the minimum CI in the class of all AoA networks having the minimum number of nodes. © 2000 John Wiley & Sons, Inc.

Algorithms for series-parallel graphs can be extended to arbitrary two-terminal dags if node reductions are used along with series and parallel reductions. A node reduction contracts a vertex with unit in-degree (out-degree) into its sole incoming (outgoing) neighbor. This paper gives an $O(n^{2.5} )$ algorithm for minimizing node reductions, based on vertex cover in a transitive auxiliary graph. Applications include the analysis of PERT networks, dynamic programming approaches to network problems, and network reliability. For NP-hard problems one can obtain algorithms that are exponential only in the minimum number of node reductions rather than the number of vertices. This gives improvements if the underlying graph is nearly series-parallel.

The greedy algorithm is a standard paradigm for solving matroid optimization problems on sequential computers. This paper presents a greedy algorithm suitable for a fully-pipelined linear array of processors, a generalization of Huang's algorithm [Hua90] for minimum spanning trees. Application of the algorithm to uniprocessor scheduling with release times and deadlines is discussed in detail. A key feature of the algorithm is its use of matroid contraction.

A theoretical study which allows determination of the minimum number of vias for realizable multilayer channel routing under a topological model is presented. The theory is sufficiently general to solve a variety of problems under different technological constraints, e.g. VLSI multilayer switchbox and channel routing, through-hole printed circuit board (PCB) channels, and single-layer routing. Topological routing is concerned with wire intersection but not area, zero-width wires and zero-area vias being assumed. Unconstrained via minimization (UVM) is not constrained to a prerouted topology. This paper presents restrictive cases of UVM, finding most to be NP-hard, but the case resulting from constraints of traditional switchbox or channel routing to be solvable in O(kn/sup 2/), where k is the maximum number of pins of a net layer and n is the number of pins. The minimum number of vias for various switchbox and channel routing benchmarks are reported.>

The matroid parity problem is a generalization of matroid intersection and general graph matching (and hence network flow, degree-constrained subgraphs, etc.). A polynomial algorithm for linear matroids was presented by Lovasz. This paper presents an algorithm that uses time 0(mn/sup 3/), where m is the number of elements and n is the rank; for the spanning tree parity problem the time 0(mn/sup 2/). The algorithm is based on the method of augmenting paths used in the algorithms for all subcases of the problem.