11378176
Minimal bricks
A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. A brick is minimal if for every edge e the deletion of e results in a graph that is not a brick. We prove a generation theorem for minimal bricks and two corollaries: (1) for n ≥ 5, every minimal brick on 2n vertices has at most 5n - 7 edges, and (2) every minimal brick has at least three vertices of degree three.
18561897
Excluding infinite minors
Let ? be an infinite cardinal, and let H be either a complete graph with ? vertices, or a tree in which every vertex has valency ?. What can we say about graphs G which (i) have no minor isomorphic to H, or (ii) contain no subgraph which is a subdivision of H?These four questions are answered for each infinite cardinal ?. In each case we find that there corresponds a necessary and sufficient structural condition (or, in some cases, several equivalent conditions) for G not to contain H in the appropriate way. We survey these results and a number of related theorems.
33726107
A menger-like property of tree-width: The finite case
The notion of tree-width was introduced by Robertson and Symour. A graph has tree-width ≦ w if it admits a tree-decomposition of tree-width ≦ w. We prove here that if G is finite and has tree-width ≦ w then it admits a tree-decomposition of tree-width ≦ w which satisfies a certain Menger-like condition. This result will be used in a future paper on well-quasi-ordering infinite graphs of bounded tree-width.
10511288
Clique Minors in Graphs and Their Complements
A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t?1 be an integer, and let G be a graph on n vertices with no minor isomorphic to Kt+1. Kostochka conjectures that there exists a constant c=c(t) independent of G such that the complement of G has a minor isomorphic to Ks, where s=?12(1+1/t)n?c?. We prove that Kostochka's conjecture is equivalent to the conjecture of Duchet and Meyniel that every graph with no minor isomorphic to Kt+1 has an independent set of size at least n/t. We deduce that Kostochka's conjecture holds for all integers t?5, and that a weaker form with s replaced by s?=?12(1+1/(2t))n?c? holds for all integers t?1.
206570580
Sachs' Linkless Embedding Conjecture
Abstract We prove Sachs′ conjecture that a graph can be embedded in 3-space so that it contains no non-trivial link (in the sense of knot theory) if and only if it contains as a minor none of the seven graphs obtainable from K 6 by Y − Δ and Δ − Y exchanges. We also show the following: (i) A graph admits such a "linkless" embedding if and only if it admits a "panelled" embedding, one such that every circuit of the graph bounds a disc disjoint from the remainder of the graph. This was a conjecture of Bohme. (ii) An embedding is panelled if and only if for every subgraph, its complement in 3-space has free fundamental group. This extends a theorem of Scharlemann and Thompson, who proved it for planar graphs. (iii) If two panelled embeddings of the same graph are "different," that is, are not related by an orientation-preserving homeomorphism of the 3-space, then there is a subgraph which is a subdivision of K 5 or K 3, 3 such that the two induced embeddings of this subgraph are still different.
2783736
List Edge-Colorings of Series-Parallel Graphs
It is proved that for every integer $k\ge3$, for every (simple) series-parallel graph $G$ with maximum degree at most $k$, and for every collection $(L(e):e\in E(G))$ of sets, each of size at least $k$, there exists a proper edge-coloring of $G$ such that for every edge $e\in E(G)$, the color of $e$ belongs to $L(e)$.
1883056
An Investigation into Keystroke Latency Metrics as an Indicator of Programming Performance
Typing has long been studied in psychology and HCI, and strong cognitive models for transcription typing exist. The goal of the present research was to test if there is any correlation between students' keystroking speed and performance while they are programming. We present the results from two studies with computer science students conducted in different contexts. Keystroke timings were recorded while they worked on Java and Ada source code. Quality of their programming work was measured mainly in terms of completeness. In the controlled experiment that lasted six hours, 39 students undertook three change tasks on a 6000 LOC Java application. In the field study, data was collected over 6 weeks from 141 students while they worked unsupervised on Ada programming in first year laboratories. In both cases there were highly significant (P=0.001), moderately strong, negative correlations between speed and coding performance. With additional development, these techniques may have promise for user modelling and assessment as well as in educational diagnostics.
3050709
Quality assurance in a student-based agile software engineering process
Agile methodologies have proven to be a popular addition to the software engineering toolbox, promising significant advances in quality for small teams, with developers no longer weighed under by the documentation said to characterise traditional approaches. Yet, in spite of these claims, quality assurance remains a question to which agile methodologies have given only a partially satisfactory answer. This work examines quality assurance practices among student developers working within a lightweight iterative development process. Our focus is upon the linkages between their reported practices and the quality levels observed in the systems delivered. The study has identified a range of approaches to improving quality for small, inexperienced teams, with applications to both the educational and SME environments.
2021116
Industry experience in migrating to object technology
Object oriented software engineering (OOSE) is becoming a common approach to software development. As third generation OOSE processes are established (e.g. OPEN (I. Graham, 1997) and the Unified Software Development Process (I. Jacobson, 1999)) organisations will start to consider OOSE as a mature technology. This recognition will mean that more organisations will go through the process of changing their current software development processes. The paper reports on the experience of one team at a large technical firm as they adopted OOSE processes for a major project. The experience of this team confirms most of what has been previously reported in the literature, and adds two additional observations. The first observation is that other literature in this field does not consider team motivation as a factor that contributes to migration success. The second observation is that other literature does not consider the relative impact of some factors over other factors.
31409070
Hermite interpolation with a pair of spirals
Abstract The Hermite interpolation problem in the plane considered here is to join two points and to match given unit tangent vectors and signed curvatures at the two points with various G 2 curves consisting of a pair of spirals. The rotation of the tangent vector of the interpolating curve from one point to the other is restricted to being less than π. The necessary and sufficient conditions for the existence of each of the various curves are given.
1283266
A guided clothoid spline
Abstract A method is described whereby a G 2 planar curve consisting of clothoid (Cornu spiral) segments, circular arcs and straight line segments is constructed. The curve passes through given points, is expressed parametrically, and has the attractive feature that the arc length and curvature are piecewise linear functions of the parameter. The given points through which the curve passes must be restricted somewhat so that a unique clothoid exists between each pair of points.