206025536
Enumerating near-4-regular maps on the sphere and the torus
In this paper rooted near-4-regular maps on the plane and the torus are counted with formulae with respect to four parameters: the root valency, the number of edges, the inner faces, and nonroot-vertex loops. In particular, the number of rooted near-4-regular maps on those surfaces with exactly k nonroot-vertex loops is investigated.
36530209
Determination of the star valency of a graph
The star valency of a graph G is the minimum, over all star decompositions π, of the maximum number of elements in π incident with a vertex. The maximum average degree of G, denoted by dmax-ave(G), is the maximum average degree of all subgraphs of G. In this paper, we prove that the star valency of G is either ⌈dmax-ave(G)/2⌉ or ⌈dmax-ave(G)/2⌉ + 1, and provide a polynomial time algorithm for determining the star valency of a graph.
43124802
On the Isomorphisms of Cayley Graphs of Abelian Groups
Let G be a finite group, S a subset of G\{1}, and let Cay (G, S) denote the Cayley digraph of G with respect to S. If, for any subset T of G\{1}, Cay(G, S) ≅ Cay(G, T) implies that Sα = T for some α ∈ Aut(G), then S is called a CI-subset. The group G is called a CIM-group if for any minimal generating subset S of G, S ∪ S-1 is a CI-subset. In this paper, CIM-abelian groups are characterized.
27650319
Generalized Bicycles
Let G = (V,E) be a graph with IZ vertices, and let A4 be a (left) module over a principal ideal domain D. Let Wo(A4) and WI(M) denote the modules of all vertex and edge weightings over M, respectively. An incidence weighting q of G is a weighting of each incident vertex-edge pair (u,e) with an element of D. Now consider an orientation of the edges of G. Let 6, denote the linear operator from We(M) to WI(M) given by 6,(w)(e) = q(u,e)w(u) yl(a,e)w(a), where e E E and u and 1: denote the tail and head of e, respectively. An v-cocycle is a weighting c E WI(M), such that c = 6(w) for some w c We(M). An q-bicycle is an q-cocycle that is also a cycle (ordinary bicycles are obtained when q E 1). Let B,(M) denote the module of all vertex weightings b E We(M), such that 6,(b) is an q-bicycle. For T a spanning tree rooted at vertex c, let q(T) denote the product of q(u,e) over all the edges e of T, where u denotes the end vertex of e that is further from u in T. The q-complexity Z~ of G is the vertex weighting over D, such that 74(c’) is the sum of q(T) over all spanning trees T rooted at t’. In this paper, we show that B,(M) ” M if, and only if 7,,m is nonzero for every nonzero m t M. Further if B,(M) 2 M then B,(M) = { z,,m : m E M}. As special cases of this formula, we obtain results about bicycles, balanced vertex weightings, resistive and leaky electrical networks, handicap ranking of tournaments, and Markov chains. The gcd q-complexity t,, is the greatest common divisor of (7411) : u E V}. We show that t, has a factorization t, = tl t2 t+l, unique up to multiplication by units of D, such that t,+l divides t, and such that for every module M over D, B,(M) is isomorphic to the direct sum of M and the submodules M(t,) = {m E A4 : t,m = 0}, i = 1,. , n 1. The latter formula generalizes the bicycle isomorphism formula given in Berman (1986).
39617215
Counting rooted near-triangulations on the sphere
This paper provides the results on the enumerations of rooted simple outerplanar maps, rooted outerplanar near-triangulations, rooted 2-connected near-triangulations, rooted strict 2-connected near-triangulations and rooted simple 2-connected near-triangulations. The answer to an open problem proposed by one of the authors is also provided.
43519756
The Number of Loopless 4-Regular Maps on the Projective Plane
In this paper rooted loopless (near) 4-regular maps on surfaces such as the sphere and the projective plane are counted and exact formulae with up to three or four parameters for such maps are given. Several classical results on regular maps and one-faced maps are deduced.
54297489
Iso-Map: Energy-Efficient Contour Mapping in Wireless Sensor Networks
Contour mapping is a crucial part of many wireless sensor network applications. Many efforts have been made to avoid collecting data from all the sensors in the network and producing maps at the sink, which is proven to be inefficient. The existing approaches (often aggregation based), however, suffer from heavy transmission traffic and incur large computational overheads on each sensor node. We propose Iso-Map, an energy-efficient protocol for contour mapping, which builds contour maps based solely on the reports collected from intelligently selected ?isoline nodes? in wireless sensor networks. Iso-Map achieves high-quality contour mapping while significantly reducing the generated traffic from O(n) to O(?n), where n is the total number of sensor nodes in the field. The pernode computation overhead is also restrained as a constant. We conduct comprehensive trace-driven simulations to verify this protocol, and demonstrate that Iso-Map outperforms the previous approaches in the sense that it produces contour maps of high fidelity with significantly reduced energy cost.
2633029
Principled strength reduction
This paper presents a principled approach for optimizing iterative (or recursive) programs. The approach formulates a loop body as a function f and a change operation ⊕, incrementalizes f with respect to ⊕, and adopts an incrementalized loop body to form a new loop that is more efficient. Three general optimizations are performed as part of the adoption; they systematically handle initializations, termination conditions, and final return values on exits of loops. These optimizations are either omitted, or done in implicit, limited, or ad hoc ways in previous methods.
9568443
A computational model for repeated pattern perception using frieze and wallpaper groups
Humans have an innate ability to perceive symmetry, but it is not obvious how to automate this powerful insight. In this paper the mathematical theory of frieze and wallpaper groups is used to extract visually meaningful building blocks (motifs) from a repeated pattern. A novel peak detection algorithm based on "regions of dominance" is used to automatically detect the underlying translational lattice of a repeated pattern. Following automatic classification of the pattern's symmetry group, knowledge of the interplay between rotation, reflection, glide-reflection and translation in that group leads to a small set of candidate motifs that exhibit local symmetry consistent with the global symmetry of the entire pattern. Although other work has addressed detection of the translational lattice of a repeated pattern, ours is the first to seek a principled method for determining a representative motif. Experiments show that the-resulting pattern motifs conform well with human perception.
10288903
Sensor Planning with Non-linear Utility Functions
Sensor planning is concerned with when to sense and what to sense. We study sensor planning in the context of planning objectives that trade-off between minimizing the worst-case, expected, and best-case plan- execution costs. Sensor planning with these planning objectives is interesting because they are realistic and the frequency of sensing changes with the planning objective: more pessimistic decision makers tend to sense more frequently. We perform sensor planning by combining one of our techniques for planning with non-linear utility functions with an existing sensor-planning method. The resulting sensor-planning method is not only as easy to implement as the sensor-planning method that it extends but also (almost) as efficient. We demonstrate empirically how sensor plans change as the planning objective changes, using a common testbed for sensor planning.
1055574
BoxScript: a component-oriented language for teaching
As component-oriented approaches become increasingly pervasive in the development of complex software systems, it becomes increasingly important to introduce computing science students to appropriate programming concepts, languages and techniques. This paper describes the design of the component-oriented language BoxScript, which seeks to address the needs of teachers and students for a clean, simple language. This paper first enumerates the principles applied in the language design and then presents the key concepts and features of BoxScript. The paper illustrates the language features by using an example and by comparing it with several other component-oriented programming languages.