Search

To carry out piping system design effectively using complicated CAD systems, such as PDMS or AM Outfitting, engineers needs some customized tool modules. This paper briefly reports the approaches taken in developing a tool system that can be integrated with PDMS, including (22.1) the network approach for equipment peripheral pipe designs and (22.2) the PDMS form development for constructing 3D piping system diagrams. Using these tools in piping system working design, engineers are actually specifying length parameters of pipe segments and orientation parameters of pipe components and let the CAD system to automatically generate the pipe models. [ABSTRACT FROM AUTHOR]

The distance between two vertices is the basis of the definition of several graph parameters including diameter, radius, average distance and metric dimension. These invariants are examined, especially how they relate to one another and to other graph invariants and their behaviour in certain graph classes. We also discuss characterizations of graph classes described in terms of distance or shortest paths. Finally, generalizations are considered. [ABSTRACT FROM AUTHOR]

The main goal of spectral graph theory is to relate important structural properties of a graph to its eigenvalues. In this chapter, we survey some old and new applications of spectral methods in graph partitioning, ranking, and epidemic spreading in networks and clustering. [ABSTRACT FROM AUTHOR]

This paper presents a novel approach to shape characterization, where a shape skeleton is modelled as a dynamic graph, and its complexity is evaluated in a dynamic evolution context. Descriptors achieved by using this approach show to be efficient in the characterization of different shape patterns with different variations in their structure (such as, occlusion, articulation and missing parts). Experiments using a generic set of shapes are presented as also a comparison with traditional shape analysis methods, such as Fourier descriptors, Curvature, Zernike moments and Bouligand-Minkowski. Although the reduced amount of information present in the shape skeleton, results show that the method is efficient for shape characterization tasks, overcoming the traditional approaches. [ABSTRACT FROM AUTHOR]

Given a finite directed graph, a coloring of its edges turns the graph into a finite-state automaton. A k-synchronizing word of a deterministic automaton is a word in the alphabet of colors at its edges that maps the state set of the automaton at least on k-element subset. A coloring of edges of a directed strongly connected finite graph of a uniform outdegree (constant outdegree of any vertex) is k-synchronizing if the coloring turns the graph into a deterministic finite automaton possessing a k-synchronizing word. For k = 1 one has the well known road coloring problem. The recent positive solution of the road coloring problem implies an elegant generalization considered first by Béal and Perrin: a directed finite strongly connected graph of uniform outdegree is k-synchronizing iff the greatest common divisor of lengths of all its cycles is k. Some consequences for coloring of an arbitrary finite digraph are presented. We describe a subquadratic algorithm of the road coloring for the k-synchronization implemented in the package TESTAS. A new linear visualization program demonstrates the obtained coloring. Some consequences for coloring of an arbitrary finite digraph and of such a graph of uniform outdegree are presented. [ABSTRACT FROM AUTHOR]

This study investigates whether pixel graphs more accurately represent percentage based data than pie graphs or bar graphs. Participants were asked to answer 24 questions each pertaining to a different graphical stimulus. Results suggest that pixel graphs are significantly better at representing large quantities of percentage based data than pie graphs. [ABSTRACT FROM AUTHOR]

In this paper, a segmentation method for spherically- and elliptically-shaped objects is presented. It utilizes a user-defined seed point to set up a directed 3D graph. The nodes of the 3D graph are obtained by sampling along rays that are sent through the surface points of a polyhedron. Additionally, several arcs and a parameter constrain the set of possible segmentations and enforce smoothness. After the graph has been constructed, the minimal cost closed set on the graph is computed via a polynomial time s-t cut, creating an optimal segmentation of the object. The presented method has been evaluated on 50 Magnetic Resonance Imaging (MRI) data sets with World Health Organization (WHO) grade IV gliomas (glioblastoma multiforme). The ground truth of the tumor boundaries were manually extracted by three clinical experts (neurological surgeons) with several years (> 6) of experience in resection of gliomas and afterwards compared with the automatic segmentation results of the proposed scheme yielding an average Dice Similarity Coefficient (DSC) of 80.37±8.93%. However, no segmentation method provides a perfect result, so additional editing on some slices was required, but these edits could be achieved quickly because the automatic segmentation provides a border that fits mostly to the desired contour. Furthermore, the manual segmentation by neurological surgeons took 2-32 minutes (mean: 8 minutes), in contrast to the automatic segmentation with our implementation that took less than 5 seconds. [ABSTRACT FROM AUTHOR]

RFID authentication protocols are susceptible to different types of relay attacks such as mafia and distance frauds. A countermeasure against these types of attacks are the well-known distance-bounding protocols. These protocols are usually designed to resist to only one of these frauds, though, behave poorly when both are considered. In this paper (i) we extend the analysis of mafia and distance frauds in recently released protocols. (ii) We introduce the concept of distance-bounding protocols based on graphs while previous proposals rely on linear registers or binary trees. (iii) We propose an instance of the graph-based protocol that resists to both mafia and distance frauds without sacrificing memory. To the best of our knowledge, this protocol achieves the best trade-off between these two frauds. [ABSTRACT FROM AUTHOR]

Face recognition is an important field that has received a lot of attention from computer vision community, with diverse set of applications in industry and science. This paper introduces a novel graph based method for face recognition which is rotation invariant. The main idea of the approach is to model the face image into a graph and use complex network methodology to extract a feature vector. We present the novel methodology and the experiments comparing it with four important and state of art algorithms. The results demonstrated that the proposed method has more positive results than the previous ones. [ABSTRACT FROM AUTHOR]

We establish a surprisingly close relationship between universal Horn classes of directed graphs and varieties generated by so-called adjacency semigroups which are Rees matrix semigroups over the trivial group with the unary operation of reversion. In particular, the lattice of subvarieties of the variety generated by adjacency semigroups that are regular unary semigroups is essentially the same as the lattice of universal Horn classes of reflexive directed graphs. A number of examples follow, including a limit variety of regular unary semigroups and finite unary semigroups with NP-hard variety membership problems. [ABSTRACT FROM AUTHOR]

Data clustering is essential problem in database technology – successful solutions in this field provide data storing and accessing optimizations, which yield better performance characteristics. Another advantage of clustering is in relation with ability to distinguish similar data patterns and semantically interconnected entities. This in turn is very valuable for data mining and knowledge discovery activities. Although many general clustering strategies and algorithms were developed in past years, this search is still far from end, as there are many potential implementation fields, each stating its own unique requirements. This paper describes data clustering based on original spatial partitioning of force-based graph layout, which provides natural way for data organization in relational databases. Practical usage of developed approach is demonstrated. [ABSTRACT FROM AUTHOR]

Name disambiguation in databases is a non-trivial task because people΄s names are often not unique and usually only a limited information is associated with each name in the database. For example, in DBLP many authors share the same name, whereas we do not have any unique identifier to distinguish them. To make it worst, we may not always be able to access the full contents of the materials, unless we have joined those organizations (e.g. ACM) who publish them. As such, how to disambiguate different names with a very limited information is a very challenging task. In this paper, we focus ourselves on such situation. We propose a term-based driven clustering approach for solving it. Specifically, we first construct some term-based taxonomies to mimic the expert knowledge of the domain by linking the related terms that appear in there automatically. Each taxonomy is then transformed into a graph, and we group the entries that belong to the same author by using either of the two novel models, namely, graph-based similarity model and graph-based random walk model. The former model aims at computing the similarity among terms, whereas the later model aims at investigating how likely would a set of terms be transformed to another set of terms. Extensive experiments are conducted by using the entries in DBLP. The favorable results indicated that our proposed approach is highly effective. [ABSTRACT FROM AUTHOR]

In this paper, we give a simple algorithm to generate all ordered trees with exactly n vertices including exactly k leaves. The best known algorithm generates such trees in O(n − k) time for each, while our algorithm generates such trees in O(1) time for each in worst case. [ABSTRACT FROM AUTHOR]

In this paper, we deal with the problem of generating all triangulations of plane graphs. We give an algorithm for generating all triangulations of a triconnected plane graph G of n vertices. Our algorithm establishes a tree structure among the triangulations of G, called the ˵tree of triangulations,″ and generates each triangulation of G in O(1) time. The algorithm uses O(n) space and generates all triangulations of G without duplications. To the best of our knowledge, our algorithm is the first algorithm for generating all triangulations of a triconnected plane graph; although there exist algorithms for generating triangulated graphs with certain properties. Our algorithm for generating all triangulations of a triconnected plane graph needs to find all triangulations of a convex polygon. We give an algorithm to generate all triangulations of a convex polygon P of n vertices in time O(1) per triangulation, where the vertices of P are numbered. Our algorithm for generating all triangulations of a convex polygon also improves previous results; existing algorithms need to generate all triangulations of convex polygons of less than n vertices before generating the triangulations of a convex polygon of n vertices. Finally, we give an algorithm for generating all triangulations of a convex polygon P of n vertices in time O(n2) per triangulation, where vertices of P are not numbered. [ABSTRACT FROM AUTHOR]

We describe for the first time how the 5-regular simple planar graphs can all be obtained from an elementary family of starting graphs by repeatedly applying a few local expansion operations. The proof uses an innovative amalgam of theory and computation. By incorporating the recursion into the canonical construction path method of isomorph rejection, a generator of non-isomorphic embedded 5-regular planar graphs is obtained with time complexity O(n2) per isomorphism class. [ABSTRACT FROM AUTHOR]

In this paper, we provide a graph-based representation of the homology (information related to the different ˵holes″ the object has) of a binary digital volume. We analyze the digital volume AT-model representation [8] from this point of view and the cellular version of the AT-model [5] is precisely described here as three forests (connectivity forests), from which, for instance, we can straightforwardly determine representative curves of ˵tunnels″ and ˵holes″, classify cycles in the complex, computing higher (co)homology operations,... Depending of the order in which we gradually construct these trees, tools so important in Computer Vision and Digital Image Processing as Reeb graphs and topological skeletons appear as results of pruning these graphs. [ABSTRACT FROM AUTHOR]

This paper proposes a graph based strategy to retrieve frames containing the queried speakers in talk show videos. Based on who is speaking and when information from the audio transcript, an initial audio-based step, that restricts the queried person to frames corresponding to when he/she is speaking, with a second step that analyzes visual features of shots is combined. Specifically, based on the production property of talk show video, (1) Shot based graph is constructed first. Then the densest sub-graph is returned as the final result. But instead of direct search (DS) of the densest part, (2) We model the intra node connection and inter node connection by a frame layer degree map to take into account the duration information within each shot node; (3)A graph partition strategy without restriction on the shape and the number of sub-graphs is proposed, in which shots containing the same person are more similar to each other. Experiments on one episode of the French talk show ˵Le Grand Echiquier″ show more than 10% improvement to audio only method and more than 7.5% improvement to DS method on average. [ABSTRACT FROM AUTHOR]

There are known crossing numbers of Cartesian products of stars with all graphs of order at most four. In this paper we are dealing with the Cartesian products of stars with graphs on five vertices. We give the exact values of crossing numbers for some of these graphs and we summarise all known results concerning crossing numbers of these graphs. In addition, we give the crossing number of the join product of star and the cycle C5 with one additional edge. [ABSTRACT FROM AUTHOR]

In this paper, we introduce our method for image retrieval to access and measuring the similarity of natural scenes by using graph semantic similarity. The proposed method is motivated by continuing effort from our previous work in adaptive image classification based on semantic concepts and edge detection. The method will learn the image information by concept occurrence vector of semantic concepts such as water, grass, sky and foliage. We constructed the graph using this information and illustrate the similarity with connecting edges. The empirical results demonstrated promising performance in terms of accuracy. [ABSTRACT FROM AUTHOR]

In this paper we propose a new approach to improve electronic editions of literary corpus, providing an efficient estimation of manuscripts pages structure. In any handwriting documents analysis process, structure recognition is an important issue. The presence of variable inter-line spaces, of inconstant base-line skews, overlappings and occlusions in unconstrained ancient 19th handwritten documents complicates the structure recognition task. Text line and fragment extraction is based on the connexity labelling of the adjacency graph at different resolution levels, for borders, lines and fragments extraction. [ABSTRACT FROM AUTHOR]

Globalization is one of the big trends in software development. Development projects need a variety of different resources with appropriate expert knowledge to be successful. More and more of these resources are nowadays obtained from specialized organizations and countries all over the world, varying in development approaches, processes, and culture. As seen with early outsourcing attempts, collaboration may fail due to these differences. Hence, the major challenge in global software engineering is to streamline collaborating organizations towards a successful conjoint development. Based on typical collaboration scenarios, this paper presents a structured approach to integrate processes in a comprehensible way. [ABSTRACT FROM AUTHOR]

This paper presents a novel methodology to shape characterization, where a shape skeleton is modeled as a dynamic graph, and degree measurements are computed to compose a set of shape descriptors. The proposed approach is evaluated in a classification experiment which considers a generic set of shapes. A comparison with traditional shape analysis methods, such as Fourier descriptors, Curvature, Zernike moments and Multi-scale Fractal Dimension, is also performed. Results show that the method is efficient for shape characterization tasks, in spite of the reduced amount of information present in the shape skeleton. [ABSTRACT FROM AUTHOR]

The network of reference frames theory explains the orientation behavior of human and non-human animals in directly experienced environmental spaces, such as buildings or towns. This includes self-localization, route and survey navigation. It is a synthesis of graph representations and cognitive maps, and solves the problems associated with explaining orientation behavior based either on graphs, maps or both of them in parallel. Additionally, the theory points out the unique role of vista spaces and asymmetries in spatial memory. New predictions are derived from the theory, one of which has been tested recently. [ABSTRACT FROM AUTHOR]

A general formulation based on the variation of digitized energy to denoise image is proposed in this paper. This method is different from classical variational method employed in image processing. For a digitized energy functional, we first compute the variation, then design algorithms leading to digital filters. Numerical experiments and comparative examples are thus carried out to verify the effectiveness of the proposed method, which is efficient, adaptive and easily implemented. Higher quality images can be obtained with characteristic singular features preserved. The method can be easily expanded to multichannel image denoising. [ABSTRACT FROM AUTHOR]

Identification of functional modules in large protein interaction networks is crucial to understand principles of cellular organization, processes and functions. As a protein can perform different functions, functional modules overlap with each other. In this paper, we presented a new algorithm OMFinder for mining overlapping functional modules in protein interaction networks by using graph split and reduction. We applied algorithm OMFinder to the core protein interaction network of budding yeast collected from DIP database. The experimental results showed that algorithm OMFinder detected many significant overlapping functional modules with various topologies. The significances of identified modules were evaluated by using functional categories from MIPS database. Most importantly, our algorithm had very low discard rate compared to other approaches of detecting overlapping modules. [ABSTRACT FROM AUTHOR]

This paper introduces a multimodal interactive system which aims to enable blind and visually impaired persons to create, manipulate and explore graph structures in a 3D space. An audio-haptic interaction paradigm has been designed to ensure a non-visual experience of graph structures. Visual feedback makes possible communication about graphs between non-sighted and sighted users. The multimodal manipulation and exploration techniques are introduced together with the system prototype. Early evaluation results are illustrated. [ABSTRACT FROM AUTHOR]

In this chapter we introduce hypergraphs as a generalisation of graphs for object representation in structural pattern recognition. We also propose extensions of algorithms for the matching and error-tolerant matching of graphs to the case of hypergraphs, including the edit distance of hypergraphs. In a series of experiments, we demonstrate the practical applicability of the proposed hypergraph matching algorithms and show some of the advantages of hypergraphs over conventional graphs. [ABSTRACT FROM AUTHOR]

A graph G is said to be fractional k-extendable if every k-matching M can be extended to a fractional perfect matching Gh with h(ε) = 1 for every ε ∈ M, where h is the indicator function of Gh. In this note, a sufficient condition for a graph to be fractional k-extendable is obtained. [ABSTRACT FROM AUTHOR]

In this article we propose a hybrid spatial model for indoor environments. The model consists of hierarchically structured graphs with typed edges and nodes. The model is hybrid in the sense that nodes and edges can be labelled with qualitative as well as quantitative information. The graphs support wayfinding and, in addition, provide helpful information for generating human-oriented descriptions of an indoor (and outdoor) path. [ABSTRACT FROM AUTHOR]

Let G be a graph of order p, and let a and b and n be nonnegative integers with 1 ≤ a ≤ b, and let g and f be two integer-valued functions defined on V (G) such that a ≤ g(x) ≤ f(x) ≤ b for all x ∈ V (G). A (g, f)-factor of graph G is defined as a spanning subgraph F of G such that g(x) ≤ dF (x) ≤ f(x) for each x ∈ V (G). Then a graph G is called a (g, f, n)-critical graph if after deleting any n vertices of G the remaining graph of G has a (g, f)-factor. In this paper, we prove that every graph G is a (g, f, n)- critical graph if its minimum degree is greater than p+a+b-2√(a + 1)p - bn + 1. Furthermore, it is showed that the result in this paper is best possible in some sense. [ABSTRACT FROM AUTHOR]