44495329
Enumeration on Nonseparable Planar Maps
Abstract This paper provides some functional equations satisfied by the generating functions for nonseparable rooted planar maps with the valency of root-vertex, the number of edges and the valency of root-faces of the maps as three parameters. But the solutions of these equations can only be obtained indirectly by considering some relations between nonseparable and general rooted planar maps. One of them is an answer to the open problem 6.1 in Liu (1983, Comb. Optim. CORR83-26, University of Waterloo).
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.
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).
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.
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.
37778003
Automatic Accurate Cost-Bound Analysis for High-Level Languages
This paper describes a language-based approach for automatic and accurate cost-bound analysis. The approach consists of transformations for building cost-bound functions in the presence of partially known input structures, symbolic evaluation of the cost-bound function based on input size parameters, and optimizations to make the overall analysis efficient as well as accurate, all at the source-language level. The calculated cost bounds are expressed in terms of primitive cost parameters. These parameters can be obtained based on the language implementation or can be measured conservatively or approximately, yielding accurate, conservative, or approximate time or space bounds. We have implemented this approach and performed a number of experiments for analyzing Scheme programs. The results helped confirm the accuracy of the analysis.
2728797
Generalized Rate Analysis for Media-Processing Platforms
In this paper we address the "rate analysis" problem for media-processing platforms consisting of multiple processor cores connected in a pipelined fashion. More precisely, we aim at determining fight bounds on the rates at which multimedia streams can be fed into such architectures. These bounds depend on architectural constraints (e.g. the available on-chip memory, bus arbitration policies, etc), as well as the application characteristics (e.g. application partitioning and mapping, workload rates generated by different tasks, etch The proposed framework for rate analysis can be used for fast design space exploration to determine how these bounds change with different architectural parameters, mapping of the application, or changing the QoS requirements associated with the input streams
6024658
Discovering Texture Regularity as a Higher-Order Correspondence Problem
Understanding texture regularity in real images is a challenging computer vision task. We propose a higher-order feature matching algorithm to discover the lattices of near-regular textures in real images. The underlying lattice of a near-regular texture identifies all of the texels as well as the global topology among the texels. A key contribution of this paper is to formulate lattice-finding as a correspondence problem. The algorithm finds a plausible lattice by iteratively proposing texels and assigning neighbors between the texels. Our matching algorithm seeks assignments that maximize both pair-wise visual similarity and higher-order geometric consistency. We approximate the optimal assignment using a recently developed spectral method. We successfully discover the lattices of a diverse set of unsegmented, real-world textures with significant geometric warping and large appearance variation among texels.
10940084
Hamiltonian Graphs with Large Neighborhood Unions
34451404
The enumeration of near-perfect matchings of factor-critical graphs
Abstract A matching of a graph is a near-perfect matching if it covers all but one vertex. A connected graph G is said to be factor-critical if G − v has perfect matchings for every vertex v of G. In this paper, the enumeration problems for near-perfect matchings in special factor-critical graphs are solved. From this, the exact values of the number of perfect matchings in special bicritical graphs are obtained.