Search results for "MathematicsofComputing_DISCRETEMATHEMATICS"
showing 10 items of 123 documents
An Investigation of the Robustness in the Travelling Salesman Problem Routes Using Special Structured Matrices
2020
In this study, the robustness of the Travelling Salesman Problem (TSP) routes is investigated by recognising the special combinatorial structures of Kalmanson matrices. A recognition algorithm encompassing three procedures based on combinatorial and linear programming (LP) is developed and executed on several randomly generated instances. These procedures produce three lower bounds which provide guarantees on the optimality of the solutions. Computational experiments show that the proposed LP-based procedure performs efficiently well across all problem dimensions and provides the best lower bounds to the TSP. This is supported by an average deviation of less than 7% between the TSP tour len…
Visualization of Large Terrain Using Non-restricted Quadtree Triangulations
2004
This paper presents a set of new techniques oriented towards the real-time visualization of large terrains. These techniques are mainly focused on semi-regular triangulations of non-restricted quadtree terrain representations. Despite the fact that the paper shows that triangulations based on non-restricted quadtrees are as simple and efficient as those based on restricted quadtrees, the new triangulations avoid discontinuity problems among the boundaries of different patches without the need for tree balancing and extra triangles addition. Another important feature of the proposed triangulation is that it incorporates an efficient method for building triangle strips and triangle fans for t…
Evolution semigroups and time operators on Banach spaces
2010
AbstractWe present new general methods to obtain shift representation of evolution semigroups defined on Banach spaces. We introduce the notion of time operator associated with a generalized shift on a Banach space and give some conditions under which time operators can be defined on an arbitrary Banach space. We also tackle the problem of scaling of time operators and obtain a general result about the existence of time operators on Banach spaces satisfying some geometric conditions. The last part of the paper contains some examples of explicit constructions of time operators on function spaces.
Temporal incoherent solitons supported by a defocusing nonlinearity with anomalous dispersion
2012
http://pra.aps.org/; International audience; We study temporal incoherent solitons in noninstantaneous response nonlinear media. Contrarily to the usual temporal soliton, which is known to require a focusing nonlinearity with anomalous dispersion, we show that a highly noninstantaneous nonlinear response leads to incoherent soliton structures which require the inverted situation: In the focusing regime (and anomalous dispersion) the incoherent wave packet experiences an unlimited spreading, whereas in the defocusing regime (still with anomalous dispersion) the incoherent wave packet exhibits a self-trapping. These counterintuitive results are explained in detail by a long-range Vlasov formu…
Weighted Adaptive Neighborhood HypergraphPartitioning for Image Segmentation
2005
International audience; The aim of this paper is to present an improvement of a previously published algorithm. The proposed approach is performed in two steps. In the first step, we generate the Weighted Adaptive Neighborhood Hypergraph (WAINH) of the given gray-scale image. In the second step, we partition the WAINH using a multilevel hypergraph partitioning technique. To evaluate the algorithm performances, experiments were carried out on medical and natural images. The results show that the proposed segmentation approach is more accurate than the graph based segmentation algorithm using normalized cut criteria.Key words hypergraph, neighborhood hypergraph, hypergraph partitioning, image…
Neighborhood Hypergraph Partitioning for Image Segmentation
2005
International audience; The aim of this paper is to introduce a multilevel neighborhoodhypergraph partitioning for image segmentation. Our proposedapproach uses the image neighborhood hypergraph model introduced inour last works and the algorithm of multilevel hypergraphpartitioning introduced by George Karypis. To evaluate the algorithmperformance, experiments were carried out on a group of gray scaleimages. The results show that the proposed segmentation approachfind the region properly from images as compared to imagesegmentation algorithm using normalized cut criteria.Key words :Graph, Hypergraph, Neighborhood hypergraph, multilevel hypergraph partitioning, image segmentation, edge dete…
k-Partite Graphs as Contexts
2018
International audience; In formal concept analysis, 2-dimensional formal contexts are bipar-tite graphs. In this work, we generalise the notions of context and concept to graphs that are not bipartite. We then study the complexity of the enumeration and identify the structure of the set of such concepts.
Vertex Distinguishing Edge- and Total-Colorings of Cartesian and other Product Graphs
2012
International audience; This paper studies edge- and total-colorings of graphs in which (all or only adjacent) vertices are distinguished by their sets of colors. We provide bounds for the minimum number of colors needed for such colorings for the Cartesian product of graphs along with exact results for generalized hypercubes. We also present general bounds for the direct, strong and lexicographic products.
Qualification de graphes sémantiques à l'aide du Model Checking
2011
National audience; Qualification de graphes sémantiques à l'aide du Model Checking
Unification of Graphs and Relations in Mizar
2020
Summary A (di)graph without parallel edges can simply be represented by a binary relation of the vertices and on the other hand, any binary relation can be expressed as such a graph. In this article, this correspondence is formalized in the Mizar system [2], based on the formalization of graphs in [6] and relations in [11], [12]. Notably, a new definition of createGraph will be given, taking only a non empty set V and a binary relation E ⊆ V × V to create a (di)graph without parallel edges, which will provide to be very useful in future articles.