Search results for " graph"

Frequency Assignment and Multicoloring Powers of Square and Triangular Meshes

2005

The static frequency assignment problem on cellular networks can be abstracted as a multicoloring problem on a weighted graph, where each vertex of the graph is a base station in the network, and the weight associated with each vertex represents the number of calls to be served at the vertex. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. In this paper, we first propose an algorithm to multicolor any weighted planar graph with at most $\frac{11}{4}W$ colors, where W denotes the weighted clique number. Next, we present a polynomial time approximation algorithm which garantees at most 2W colors for multicoloring a power square mesh. Fur…

Graph Connectivity, Monadic NP and built-in relations of moderate degree

1995

It has been conjectured [FSV93] that an existential secondoder formula, in which the second-order quantification is restricted to unary relations (i.e. a Monadic NP formula), cannot express Graph Connectivity even in the presence of arbitrary built-in relations.

Online Scheduling of Task Graphs on Heterogeneous Platforms

2020

Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}$ 4 m / k -competitive online algorithm by Amaris et al. [1] , where $m$ m is the number of CPUs and $k$ k the number of GPUs ( $m\geq k$ m ≥ k ). We prove that no online…

Finitary Representations and Images of Transitive Finitary Permutation Groups

1999

Abstract We characterize the point stabilizers and kernels of finitary permutation representations of infinite transitive groups of finitary permutations. Moreover, the number of such representations is determined.

Counterexamples to the Algebraic Closed Graph Theorem

1982

The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs

2016

Nowadays there are many social media sites with a very large number of users. Users of social media sites and relationships between them can be modelled as a graph. Such graphs can be analysed using methods from social network analysis (SNA). Many measures used in SNA rely on computation of shortest paths between nodes of a graph. There are many shortest path algorithms, but the majority of them suits only for small graphs, or work only with road network graphs that are fundamentally different from social graphs. This paper describes an efficient shortest path searching algorithm suitable for large social graphs. The described algorithm extends the Atlas algorithm. The proposed algorithm so…

Assonanze ritmiche tra movimento grafico e segno digitale

2015

L’accostamento di più lettere costruisce nuove parole, significanti e concetti. Quando a queste lettere si associa l’idea di suono si disegna la forma degli oggetti. Schopenhauer fondò la sua teoria dei colori sulla bipartizione dell’attività della retina, paragonandola alla scala musicale, in quanto i colori erano posti in un rapporto numerico razionale tra loro. Pierre Boulez, partendo dall’opera e dalle lezioni di Paul Klee al Bauhaus, sviluppa una riflessione sulla distribuzione e sul ritmo dello spazio musicale; infatti nella serie di incisioni o di quadri come Le città, la simmetria, più che un paesaggio urbano, evoca un rigo musicale con le linee disegnate dalle note distribuite sott…

Object Clustering Methods and a Query Decomposition Strategy for Distributed Object-Based Information Systems

1999

Emerging developments and advances in distributed processing have created a need for tools and methods to partition and distribute information systems across interconnected processors. In particular, distribution approaches which take into account the key characteristics of OO concepts are required to extend traditional fragmentation results to object oriented database systems. To fulfill the above requirements, we propose a methodology for the distribution design of object-based information systems. The underlying approach consists of techniques and heuristics that can be used to create clusters of inter-related object classes that can be fragmented interdependently, producing distribution…

Pharmacological distribution diagrams: a tool for de novo drug design.

1996

Abstract Discriminant analysis applied to SAR studies using topological descriptors allows us to plot frequency distribution diagrams: a function of the number of drugs within an interval of values of discriminant function vs. these values. We make use of these representations, pharmacological distribution diagrams (PDDs), in structurally heterogeneous groups where generally they adopt skewed Gaussian shapes or present several maxima. The maxima afford intervals of discrimianant function in which exists a good expectancy to find new active drugs. A set of β-blockers with contrasted activity has been selected to test the ability of PDDs as a visualizing technique, for the identification of n…

Programming languages for data-Intensive HPC applications: A systematic mapping study

2020

This work is a result of activities from COST Action 10406 High -Performance Modelling and Simulation for Big Data Applications (cHiPSet), funded by the European Cooperation in Science and Technology. FCT, Portugal for grants: NOVA LINCS Research Laboratory Ref. UID/ CEC/ 04516/ 2019); INESC-ID Ref. UID/CEC/50021/2019; BioISI Ref. UID/MULTI/04046/2103; LASIGE Research Unit Ref. UID/CEC/00408/ 2019. A major challenge in modelling and simulation is the need to combine expertise in both software technologies and a given scientific domain. When High-Performance Computing (HPC) is required to solve a scientific problem, software development becomes a problematic issue. Considering the complexity…