Approximation algorithms for some graph partitioning problems.
Approximation algorithms for the design of SDH/SONET networks
In this paper, a graph partitioning problem that arises in the design of SONET/SDH networks is defined and formalized. Approximation algorithms with performance guarantees are presented. To solve this problem efficiently in practice, fast greedy algorithms and a tabu-search method are proposed and analyzed by means of an experimental study.
Approximation algorithms for the design of SDH/SONET networks
In this paper, a graph partitioning problem that arises in the design of SONET/SDH networks is defined and formalized. Approximation algorithms with performance guarantees are presented. To solve this problem efficiently in practice, fast greedy algorithms and a tabu-search method are proposed and analyzed by means of an experimental study.
Approximation algorithms for the traveling salesman problem with range condition
Approximation Algorithms for the Traveling Salesman Problem with Range Condition
We prove that the Christofides algorithm gives a approximation ratio for the special case of traveling salesman problem (TSP) in which the maximum weight in the given graph is at most twice the minimum weight for the odd degree restricted graphs. A graph is odd degree restricted if the number of odd degree vertices in any minimum spanning tree of the given graph is less than times the number of vertices in the graph. We prove that the Christofides algorithm is more efficient (in terms...
Approximation des dissimilarités par des arbres additifs
Approximations of weighted independent set and hereditary subset problems.
Arbitrarily traceable Eulerian graph has the Hamiltonian square
Arbitrarily vertex decomposable caterpillars with four or five leaves
A graph G of order n is called arbitrarily vertex decomposable if for each sequence (a₁,...,aₖ) of positive integers such that a₁+...+aₖ = n there exists a partition (V₁,...,Vₖ) of the vertex set of G such that for each i ∈ 1,...,k, induces a connected subgraph of G on vertices. D. Barth and H. Fournier showed that if a tree T is arbitrarily vertex decomposable, then T has maximum degree at most 4. In this paper we give a complete characterization of arbitrarily vertex decomposable caterpillars...
Arbology: Trees and pushdown automata
We present a unified and systematic approach to basic principles of Arbology, a new algorithmic discipline focusing on algorithms on trees. Stringology, a highly developed algorithmic discipline in the area of string processing, can use finite automata as its basic model of computation. For various kinds of linear notations of ranked and unranked ordered trees it holds that subtrees of a tree in a linear notation are substrings of the tree in the linear notation. Arbology uses pushdown automata...
Arboreal structure and regular graphs of median-like classes
We consider classes of graphs that enjoy the following properties: they are closed for gated subgraphs, gated amalgamation and Cartesian products, and for any gated subgraph the inverse of the gate function maps vertices to gated subsets. We prove that any graph of such a class contains a peripheral subgraph which is a Cartesian product of two graphs: a gated subgraph of the graph and a prime graph minus a vertex. Therefore, these graphs admit a peripheral elimination procedure which is a generalization...
Arbres binaires de recherche : propriétés combinatoires et applications
Arbres minimals i arbres de Steiner en la mètrica rectilínea.
Usando la métrica rectilínea (oL1) se tratan algunos aspectos del problema clásico de hallar el árbol de coste mínimo que enlaza un conjunto dado de P puntos en el plano.En primer lugar se recuerdan las propiedades fundamentales de los árboles de Steiner dado que éstos son la solución general al problema enunciado. A partir de unas observaciones sobre la acotación de su longitud máxima cuando P se halla en el interior de un cuadrado Q de lado unidad, se obtiene -para el mismo caso- una cota superior...
Arbres minimums communs et compatibilité de données de types variés
Architectonics of Alain Lascoux's preferred formulas. (Architectonique des formules préférées d'Alain Lascoux.)
Arcs with large conical subsets.
Arc-transitive and s-regular Cayley graphs of valency five on Abelian groups
Let G be a finite group, and let . A Cayley di-graph Γ = Cay(G,S) of G relative to S is a di-graph with a vertex set G such that, for x,y ∈ G, the pair (x,y) is an arc if and only if . Further, if , then Γ is undirected. Γ is conected if and only if G = ⟨s⟩. A Cayley (di)graph Γ = Cay(G,S) is called normal if the right regular representation of G is a normal subgroup of the automorphism group of Γ. A graph Γ is said to be arc-transitive, if Aut(Γ) is transitive on an arc set. Also, a graph Γ...
Arc-transitive non-Cayley graphs from regular maps.
Area distribution and scaling function for punctured polygons.
Area Requirement and Symmetry Display of Planar Upward Drawings.