Maximizing the distance between center,centroid and characteristic set of a tree

Consider a tree P_n-g,g , n≥ 2, 1≤ g≤ n-1 on n vertices which is obtained from a path on [1,2,?…?,n-g] vertices by adding g pendant vertices to the pendant vertex n-g. We prove that over all trees on n?≥?5 vertices, the distance between center and characteristic set, centroid and characteristic set, and center and centroid is maximized by trees of the form P_n-g,g , 2?≤?g?≤?n-3. For n≥ 5, we also supply the precise location of the characteristic set of the tree P_n-g,g , 2?≤?g?≤?n-3.     

Joining caterpillars and stability of the tree center

The path-tableP(T) of a tree T collects information regarding the paths in T: for each vertex v, the row of P(T) relative to v lists the number of paths containing v of the various lengths. We call this row the path-row of v in T.Two trees having the same path-table (up to reordering the rows) are called path-congruent (or path-isomorphic).Motivated by Kelly-Ulam's Reconstruction Conjecture and its variants, we have looked for new necessary and sufficient conditions for isomorphisms between two trees.Path-congruent trees need not be isomorphic, although they are similar in some respects. In [P. Dulio, V. Pannone, Trees with path-stable center, Ars Combinatoria, LXXX (2006) 153-175] we have introduced the concepts of trunkTr(T) of a tree T and ramification of a vertex v∈V(Tr(T)), and proved that, if the ramification of the central vertices attains its minimum or maximum value, then the path-row of a central vertex is “unique”, i.e. it is different from the path-row of any non-central vertex (in fact, this uniqueness property of a central path-row holds for all trees of diameter less than 8, regardless of the ramification values).In this paper we prove that, for all other values of the ramification, and for all diameters greater than 7, there are trees in which the above uniqueness fails.     

A characterization of the average tree solution for tree games

For the class of tree games, a new solution called the average tree solution has been proposed recently. We provide a characterization of this solution. This characterization underlines an important difference, in terms of symmetric treatment of the agents, between the average tree solution and the Myerson value for the class of tree games.     

A linear algorithm for a core of a tree

A core of a graph G is a path P in G that is central with respect to the property of minimizing d(P) = Σ_υ?V(G)d(υ, P), where d(υ, P) is the distance from vertex υ to path P. We present a linear algorithm for finding a core of a tree. Since the core of a graph is not necessarily unique, we also output a list of all the vertices which are in some core.     

A phase transition for the heights of a fragmentation tree

We provide information about the asymptotic regimes for a homogeneous fragmentation of a finite set. We establish a phase transition for the asymptotic behavior of the shattering times, defined as the first instants when all the blocks of the partition process have cardinality less than a fixed integer. Our results may be applied to the study of certain random split trees. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 247‐274, 2011     

A formula for the Euler characteristic of a real algebraic manifold

There is given an algebraic formula which expresses the Euler characteristic of a real algebraic manifold in terms of the signature of an appropriate bilinear form. Supported by grant KBN 2/1125/91/01     

A new parallel algorithm for rooting a tree

When an undirected tree,T, and a vertex,r, in the tree are given, the problem to transformT into a rooted tree withr as its root is considered. Using Euler tour and prefix sum, an optimal algorithm has been developed [2, 3]. We will present another parallel algorithm which is optimal also on EREW PRAM. Our approach reduces the given tree step by step by pruning and pointer jumping. That is, the tree structure is retained during algorithm processing such that another tree computations can be carried out in parallel.     

A sophisticated expert system for the diagnosis of a CNC machining center

As the domains of diagnostic expert systems become larger and more complex, purely associative approaches are no longer adequate solutions. A good example for such a situation is the diagnosis of a CNC machining center where the diagnostic process has a rich inner structure that has to be reflected in the system. In this article we describe three ways of extending the conventional expert system architecture. Firstly, our system uses a structural model of the machining center in addition to production rules. Secondly, we pay special attention to knowledge acquisition which is intimately related to the learning process. Finally, several temporal aspects of the diagnostic situation are addressed explicitly.

---

Zusammenfassung Im gleichen Maße, wie diagnostische Expertensysteme in immer umfangreichere und komplexere Aufgabenstellungen vordringen, zeigt sich, daß ausschließlich regelbasierte, assoziative Ansätze keine angemessene Lösung mehr darstellen. Ein typisches Beispiel für eine solche Situation ist die Diagnose von CNC-Bearbeitungszentren, deren komplexe innere Struktur und die spezifische Vorgehensweise des Experten explizit in der Wissensbasis repräsentiert werden müssen. In diesem Artikel beschreiben wir drei Richtungen, in denen diekonventionelle Expertensystemarchitektur erweitert werden kann, um den gestiegenen Anforderungen zu entsprechen. Unser System stützt sich auf ein Struktur- und Funktionsmodell des Bearbeitungszentrums, das das in Regelform gespeicherte Wissen ergänzt. Die Verwendung des Modells stellt neuartige Anforderungen an die Wissensakquisition, die durch eine enge Verzahnung mit dem Lernmechanismus des Expertensystems unterstützt wird. Schließlich gehen wir auf die zeitlichen Aspekte der Diagnosesituation ein, die eine spezielle Behandlung der dynamischen Maschinenprozesse und der sich darin entwickelnden Fehler erfordern.

     

A scaling technique for finding the weighted analytic center of a polytope

Let a bounded full dimensional polytope be defined by the systemAx b whereA is anm × n matrix. Leta _i denote theith row of the matrixA, and define theweighted analytic center of the polytope to be the point that minimizes the strictly convex barrier function – _i=1 ^m w _i ln(a _i ^T x –b _i ). The proper selection of weightsw _i can make any desired point in the interior of the polytope become the weighted analytic center. As a result, the weighted analytic center has applications in both linear and general convex programming. For simplicity we assume that the weights are positive integers.If some of thew _i 's are much larger than others, then Newton's method for minimizing the resulting barrier function is very unstable and can be very slow. Previous methods for finding the weighted analytic center relied upon a rather direct application of Newton's method potentially resulting in very slow global convergence. We present a method for finding the weighted analytic center that is based on the scaling technique of Edmonds and Karp and is an enhancement of Newton's method. The scaling algorithm runs in iterations, wherem is the number of constraints defining the polytope andW is the largest weight given on any constraint. Each iteration involves taking a step in the Newton direction and its complexity is dominated by the time needed to solve a system of linear equations.Supported by the Campus Research Board, University of Illinois at Urbana-Champaign.Supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195.     

Reverse selective obnoxious center location problems on tree graphs

In this paper, we investigate a variant of the reverse obnoxious center location problem on a tree graph \(T=(V,E)\) in which a selective subset of the vertex set V is considered as locations of the existing customers. The aim is to augment or reduce the edge lengths within a given budget with respect to modification bounds until a predetermined undesirable facility location becomes as far as possible from the customer points under the new edge lengths. An \({\mathcal {O}}(|E|^2)\) time combinatorial algorithm is developed for the problem with arbitrary modification costs. For the uniform-cost case, one obtains the improved \({\mathcal {O}}(|E|)\) time complexity. Moreover, optimal solution algorithms with \({\mathcal {O}}(|E|^2)\) and \({\mathcal {O}}(|E|)\) time complexities are proposed for the integer version of the problem with arbitrary and uniform cost coefficients, respectively.     

A cohomological characteristic for the length and width of a partially ordered set

Grothendieck topologies on a poset preset by one set and corresponding sheaf cohomologies are analyzed. The relation between the given cohomologies and the length of a poset is identified. For this purpose, Grothendieck topologies are defined on the set of the chains and antichains of the given poset; the corresponding theories of sheaf cohomologies are formed and with the help of those the poset is analyzed.     

A criterion for quasi-heredity and the characteristic module

The aim of this paper is to give a criterion for quasi-heredity by the existence of a faithful module, and a test for the characteristic module by using a property of faithful and partial tilting. Supported by the National Education Committee of China, the Chinese Academy of Science and the National Natural Science Foundation of China     

A geometric criterion for the boundedness of characteristic classes

We show that for a connected Lie group G, the linearity of its radical \({\sqrt G}\) (that is of its biggest connected normal solvable subgroup), is a necessary and sufficient condition for the boundedness of all Borel cohomology classes of G with integer coefficients, and that the linearity of \({\sqrt G}\) is also equivalent to a large-scale geometric property of G (involving distortion).