Academic literature on the topic 'Parametrized graphs'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Parametrized graphs.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Parametrized graphs"
1
Faran, Rachel, and Orna Kupferman. "A Parametrized Analysis of Algorithms on Hierarchical Graphs." International Journal of Foundations of Computer Science 30, no. 06n07 (September 2019): 979–1003. http://dx.doi.org/10.1142/s0129054119400252.
Full textAbstract:
Hierarchical graphs are used in order to describe systems with a sequential composition of sub-systems. A hierarchical graph consists of a vector of subgraphs. Vertices in a subgraph may “call” other subgraphs. The reuse of subgraphs, possibly in a nested way, causes hierarchical graphs to be exponentially more succinct than equivalent flat graphs. Early research on hierarchical graphs and the computational price of their succinctness suggests that there is no strong correlation between the complexity of problems when applied to flat graphs and their complexity in the hierarchical setting. That is, the complexity in the hierarchical setting is higher, but all “jumps” in complexity up to an exponential one are exhibited, including no jumps in some problems. We continue the study of the complexity of algorithms for hierarchical graphs, with the following contributions: (1) In many applications, the subgraphs have a small, often a constant, number of exit vertices, namely vertices from which control returns to the calling subgraph. We offer a parameterized analysis of the complexity and point to problems where the complexity becomes lower when the number of exit vertices is bounded by a constant. (2) We describe a general methodology for algorithms on hierarchical graphs. The methodology is based on an iterative compression of subgraphs in a way that maintains the solution to the problems and results in subgraphs whose size depends only on the number of exit vertices, and (3) we handle labeled hierarchical graphs, where edges are labeled by letters from some alphabet, and the problems refer to the languages of the graphs.
2
ELLIS-MONAGHAN, JOANNA A., and LORENZO TRALDI. "Parametrized Tutte Polynomials of Graphs and Matroids." Combinatorics, Probability and Computing 15, no. 06 (August 10, 2006): 835. http://dx.doi.org/10.1017/s0963548306007656.
Full text
3
Asaeda, Marta, and Uffe Haagerup. "Fusion rules on a parametrized series of graphs." Pacific Journal of Mathematics 253, no. 2 (December 31, 2011): 257–88. http://dx.doi.org/10.2140/pjm.2011.253.257.
Full text
4
Sadeghian, Ali, Mohammadreza Armandpour, Anthony Colas, and Daisy Zhe Wang. "ChronoR: Rotation Based Temporal Knowledge Graph Embedding." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 7 (May 18, 2021): 6471–79. http://dx.doi.org/10.1609/aaai.v35i7.16802.
Full textAbstract:
Despite the importance and abundance of temporal knowledge graphs, most of the current research has been focused on reasoning on static graphs. In this paper, we study the challenging problem of inference over temporal knowledge graphs. In particular, the task of temporal link prediction. In general, this is a difficult task due to data non-stationarity, data heterogeneity, and its complex temporal dependencies. We propose Chronological Rotation embedding (ChronoR), a novel model for learning representations for entities, relations, and time. Learning dense representations is frequently used as an efficient and versatile method to perform reasoning on knowledge graphs. The proposed model learns a k-dimensional rotation transformation parametrized by relation and time, such that after each fact's head entity is transformed using the rotation, it falls near its corresponding tail entity. By using high dimensional rotation as its transformation operator, ChronoR captures rich interaction between the temporal and multi-relational characteristics of a Temporal Knowledge Graph. Experimentally, we show that ChronoR is able to outperform many of the state-of-the-art methods on the benchmark datasets for temporal knowledge graph link prediction.
5
Keros, Alexandros D., Vidit Nanda, and Kartic Subr. "Dist2Cycle: A Simplicial Neural Network for Homology Localization." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 7 (June 28, 2022): 7133–42. http://dx.doi.org/10.1609/aaai.v36i7.20673.
Full textAbstract:
Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations between vertices at different resolutions, all at once. This concept is central towards detection of higher dimensional topological features of data, features to which graphs, encoding only pairwise relationships, remain oblivious. While attempts have been made to extend Graph Neural Networks (GNNs) to a simplicial complex setting, the methods do not inherently exploit, or reason about, the underlying topological structure of the network. We propose a graph convolutional model for learning functions parametrized by the k-homological features of simplicial complexes. By spectrally manipulating their combinatorial k-dimensional Hodge Laplacians, the proposed model enables learning topological features of the underlying simplicial complexes, specifically, the distance of each k-simplex from the nearest "optimal" k-th homology generator, effectively providing an alternative to homology localization.
6
LEFLOCH, PHILIPPE G. "GRAPH SOLUTIONS OF NONLINEAR HYPERBOLIC SYSTEMS." Journal of Hyperbolic Differential Equations 01, no. 04 (December 2004): 643–89. http://dx.doi.org/10.1142/s0219891604000287.
Full textAbstract:
For nonlinear hyperbolic systems of partial differential equations in one-space dimension (in either conservative or non-conservative form) we introduce a geometric framework in which solutions are sought as (continuous) parametrized graphs(t,s) ↦ (X,U)(t,s) satisfying ∂sX ≥ 0, rather than (discontinuous) functions (t,x) ↦ u(t,x). On one hand, we generalize an idea by Dal Maso, LeFloch, and Murat who used a family of traveling wave profiles to define non-conservative products, and we define the notion of graph solution subordinate to a family of Riemann graphs. The latter naturally encodes the graph of the solution to the Riemann problem, which should be determined from an augmented model taking into account small-scale physics and providing an internal structure to the shock waves. In a second definition, we write an evolution equation on the graphs directly and we introduce the notion of graph solution subordinate to a diffusion matrix, which merges together the hyperbolic equations (in the "non-vertical" parts of the graphs) with the traveling wave equation of the augmented model (in the "vertical" parts). We consider the Cauchy problem within the class of graph solutions. The graph solution to the Cauchy problem is constructed by completion of the discontinuities of the entropy solution. The uniqueness is established by applying a general uniqueness theorem due to Baiti, LeFloch, and Piccoli. The proposed geometric framework illustrates the importance of the uniform distance between graphs to deal with solutions of nonlinear hyperbolic problems.
7
Hussein, Amru. "Sign-indefinite second-order differential operators on finite metric graphs." Reviews in Mathematical Physics 26, no. 04 (May 2014): 1430003. http://dx.doi.org/10.1142/s0129055x14300039.
Full textAbstract:
The question of self-adjoint realizations of sign-indefinite second-order differential operators is discussed in terms of a model problem. Operators of the type [Formula: see text] are generalized to finite, not necessarily compact, metric graphs. All self-adjoint realizations are parametrized using methods from extension theory. The spectral and scattering theories of the self-adjoint realizations are studied in detail.
8
Aristoff, David, and Lingjiong Zhu. "On the phase transition curve in a directed exponential random graph model." Advances in Applied Probability 50, no. 01 (March 2018): 272–301. http://dx.doi.org/10.1017/apr.2018.13.
Full textAbstract:
Abstract We consider a family of directed exponential random graph models parametrized by edges and outward stars. Much of the important statistical content of such models is given by the normalization constant of the models, and, in particular, an appropriately scaled limit of the normalization, which is called the free energy. We derive precise asymptotics for the normalization constant for finite graphs. We use this to derive a formula for the free energy. The limit is analytic everywhere except along a curve corresponding to a first-order phase transition. We examine unusual behavior of the model along the phase transition curve.
9
Stefanou, Anastasios. "Tree decomposition of Reeb graphs, parametrized complexity, and applications to phylogenetics." Journal of Applied and Computational Topology 4, no. 2 (February 27, 2020): 281–308. http://dx.doi.org/10.1007/s41468-020-00051-1.
Full text
10
Galvez, Carmen, and Félix Moya-Anegón. "The unification of institutional addresses applying parametrized finite-state graphs (P-FSG)." Scientometrics 69, no. 2 (November 2006): 323–45. http://dx.doi.org/10.1007/s11192-006-0156-3.
Full textDissertations / Theses on the topic "Parametrized graphs"
1
Sérée, Bastien. "Problèmes d'optimisation des les graphes paramétrés." Electronic Thesis or Diss., Ecole centrale de Nantes, 2022. http://www.theses.fr/2022ECDN0066.
Full textAbstract:
Nous considérons des graphes orientés pondérés dont l’énergie est paramétrée. Nous proposons dans un premier temps un algorithme qui, étant donné un graphe et un de ses sommets, renvoie des arbres, chaque arbre représentant les plus courtschemins depuis la source vers tous les autres sommets du graphe pour une zone particulière de l’espace des paramètres. De plus l’union de ces zones couvre l’espace des paramètres. Nous considérons ensuite l’accessibilité dans les graphes à énergie multidimensionnelle, avec un type de contraintes plus absolues qui imposent que l’énergie reste entre des bornes. Nous montrons la décidabilité et la complexité du problème quel que soit le nombre de paramètres et de dimensions lorsque les paramètres prennent des valeurs entières. Nous montrons également l’indécidabilité de ce problème avec au moins un paramètre lorsque la dimension est supérieure ou égale à deux. Nous étudions enfin des jeux de parité à un et deux joueurs sur les graphes paramétrés dont l’objectif est la conjonction d’une condition qualitative sur la parité et d’une condition quantitative : l’énergiedoit rester positive. Nous montrons la décidabilité et prouvons des bornes de la complexité du problème de la recherche d’une stratégie gagnante dans les cas à un et à deux joueursWe are considering weighted oriented graphs with parametrized energy. Firstly we propose an algorithm that, given a graph and one of its vertices, returns trees, every tree representing shortest-paths from the source to every other vertex for a particular zone of the parameter space. Moreover, union of these zones is a covering of the parameter space. Then we consider reachability in graphs with multi-dimensional energy, with stricter constraints that enforce the energy to stay between bounds. We prove decidabilty and complexity of this problem regardless of the dimension and the number of parameters when parameters take integer values. We alsoprove the undecidability of this problem when there is at least one parameter and the dimension is at least two. Finally we study paritygames on parametrized graphs with one and two players whose objective is the conjunction of a qualitative condition on the parity andquantitative one : energy must stay positive. We show the decidability and prove bounds on the complexity of the problem of searchinga winning strategy in both cases with one and two players
2
Frasca, M. "GRAPH-BASED APPROACHES FOR IMBALANCED DATA IN FUNCTIONAL GENOMICS." Doctoral thesis, Università degli Studi di Milano, 2012. http://hdl.handle.net/2434/172445.
Full textAbstract:
The Gene Function Prediction (GFP) problem consists in inferring biological properties for the genes whose function is unknown or only partially
known, and raises challenging issues from both a machine learning and a
computational biology standpoint.
The GFP problem can be formalized as a semi-supervised learning problem in an undirected graph. Indeed, given a graph with a partial graph labeling, where nodes represent genes, edges functional relationships between
genes, and labels their membership to functional classes, GFP consists in
inferring the unknown functional classes of genes, by exploiting the topological relationships of the networks and the available a priori knowledge about
the functional properties of genes.
Several network-based machine learning algorithms have been proposed
for solving this problem, including Hopfield networks and label propagation
methods; however, some issues have been only partially considered, e.g. the
preservation of the prior knowledge and the unbalance between positive and
negative labels.
A first contribution of the thesis is the design of a Hopfield-based cost
sensitive neural network algorithm (COSNet) to address these learning issues. The method factorizes the solution of the problem in two parts: 1) the
subnetwork composed by the labelled vertices is considered, and the network
parameters are estimated through a supervised algorithm; 2) the estimated
parameters are extended to the subnetwork composed of the unlabeled vertices, and the attractor reached by the dynamics of this subnetwork allows
to predict the labeling of the unlabeled vertices.
The proposed method embeds in the neural algorithm the “a priori”
knowledge coded in the labeled part of the graph, and separates node labels
and neuron states, allowing to differentially weight positive and negative
node labels, and to perform a learning approach that takes into account the
“unbalance problem” that affects GFP.
A second contribution of this thesis is the development of a new algorithm (LSI ) which exploits some ideas of COSNet for evaluating the predictive capability of each input network. By this algorithm we can estimate the
effectiveness of each source of data for predicting a specific class, and then
we can use this information to appropriately integrate multiple networks by
weighting them according to an appropriate integration scheme.
Both COSNet and LSI are computationally efficient and scale well with
the dimension of the data.
COSNet and LSI have been applied to the genome-wide prediction of gene functions in the yeast and mouse model organisms, achieving results
comparable with those obtained with state-of-the-art semi-supervised and
supervised machine learning methods.
3
Santos, Eduardo Toledo. "Extensões ao algoritmo de 'RAY TRACING' parametrizado." Universidade de São Paulo, 1998. http://www.teses.usp.br/teses/disponiveis/3/3142/tde-13022004-114755/.
Full textAbstract:
Ray tracing é um algoritmo para a síntese de imagens por computador. Suas características principais são a alta qualidade das imagens que proporciona (incorporando sombras, reflexões e transparências entre outros efeitos) e, por outro lado, a grande demanda em termos de processamento. O ray tracing parametrizado é um algoritmo baseado no ray tracing, que permite a obtenção de imagens com a mesma qualidade a um custo computacional dezenas de vezes menor, porém com restrições. Estas restrições são a necessidade de geração de um arquivo de dados inicial, cujo tempo de processamento é pouco maior que o do ray tracing convencional e a não possibilidade de alteração de qualquer parâmetro geométrico da cena. Por outro lado, a geração de versões da mesma cena com mudanças nos parâmetros ópticos (cores, intensidades de luz, texturas, reflexões, transparências, etc.) é extremamente rápida. Esta tese propõe extensões ao algoritmo de ray tracing parametrizado, procurando aliviar algumas de suas restrições. Estas extensões permitem alterar alguns parâmetros geométricos como a posição das fontes de luz, parâmetros de fontes de luz spot e mapeamento de revelo entre outros, mantendo o bom desempenho do algoritmo original. Também é estudada a paralelização do algoritmo e outras formas de aceleração do processamento. As extensões propostas permitem ampliar o campo de aplicação do algoritmo original incentivando sua adoção mais generalizada.Ray tracing is an image synthesis computer algorithm. Its main features are the high quality of the generated images (which incorporate shadows, reflections and transparency, among other effects) and, on the other hand, a high processing demand. Parameterized ray tracing is an algorithm based on ray tracing which allows the synthesis of images with the same quality but tens of times faster than ray tracing, although with some restrictions. These restrictions are the requirement of generating a data file (which takes a little longer than standard ray tracing to create) and the fact that no geometric modifications are allowed. On the other side, the processing time for creating new versions of the image with changes only on optical parameters (colors, light intensities, textures, reflections, transparencies, etc.) is extremely fast. This Ph.D. dissertation proposes extensions to the parameterized ray tracing algorithm for diminishing its restrictions. These extensions allow changing some geometric parameters like the light source positions, spotlight parameters and bump-mapping among others, keeping the processing performance of the original algorithm. The parallelization of the algorithm is also focused as well as other performance enhancements. The proposed extensions enlarge the field of application of the original algorithm, encouraging more general adoption.
4
Martins, Nicolas de Almeida. "Problemas de coloraÃÃo de grafos com poucos P4Âs." Universidade Federal do CearÃ, 2013. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=9723.
Full textAbstract:
Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgicoOs problemas de coloraÃÃo estÃo entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importÃncia teÃrica e prÃtica. O problema da L(2,1)-coloraÃÃo, por exemplo, pode ser aplicado na atribuiÃÃo de frequÃncias de rÃdio a torres de transmissÃo visando a diminuiÃÃo de interferÃncias nas transmissÃes. No entanto a maior parte das coloraÃÃes de Grafos à de difÃcil resoluÃÃo(NP-DifÃceis). Nesta dissertaÃÃo, estudamos os problemas de L(2,1)-coloraÃÃo, coloraÃÃo harmÃnica e M-partiÃÃo. Tendo em vista que os problemas de coloraÃÃo abordados nesta dissertaÃÃo sÃo todos NP-difÃceis, decidimos estudar as restriÃÃes destes problemas a (q,q-4)-grafos , com q fixo. As soluÃÃes utilizam a decomposiÃÃo primeval destes grafos. Ressaltamos ainda que esta classe contÃm os cografos e os grafos P4-esparsos. Os algoritmos encontrados desta maneira sÃo chamados de Fixed Parameter Tractable(FPT), pois sÃo polinomiais quando consideramos um determinado parÃmetro como um valor fixo. AlÃm da obtenÃÃo de algoritmos para diversos problemas de coloraÃÃo restritos aos (q,q-4)-grafos, com q fixo, tambÃm avaliamos a Conjectura de Griggs-Yeh com relaÃÃo aos grafos P_4-Esparsos e P_4-Laden.
The coloring problems are among the most studied in the graph theory due to its great theoretical and practical importance. The L(2;1)-labeling problem, for instance, can be applied to the frequency assignment of transmission towers in order to decrease interference in transmissions. However most of the graph coloring problems are difficult to solve (NP-hard). In this thesis, we study the L(2;1)-coloring, the harmonious coloring and M-partition of graphs. Considering that the coloring problems addressed in this thesis are all NP-hard, we decided to study the restrictions of these problems to (q;q4)-graphs, with q fixed. The solutions use the Primeval decomposition of these graphs. We also emphasize that this class contains the cographs and P4-sparse graphs. The algorithms found in this way are called Fixed parameter tractable (FPT), because they run on polynomial time if we consider a certain parameter as a fixed value. Besides obtaining algorithms for several coloring problems restricted to (q;q4)-graphs, with q fixed, we also evaluated Conjecture of Griggs-Yeh graphs with respect to P4-Sparse and P4-Laden graphs.
5
Majewska, Gabriela. "Beta-skeletons - parametrized proximity graphs." Doctoral thesis, 2016.
Find full textAbstract:
In this dissertation, we show various results of our research on β-skeletons. The β-skeletons are graphs introduced first by Kirkpatrick and Radke, that belong to the family of proximity graphs, geometric graphs in which two vertices are connected with an edge if and only if they satisfy particular geometric requirements. For β-skeletons such edge between points v_1 and v_2 exists if no point from a given set lies inside a set called β-neighborhood (β-lune, respectively) of v_1 and v_2. Based on the shape of this set, we get two families of β-skeletons: lune-based β-skeletons and circle-based β-skeletons. β-skeletons find their applications in various areas: in machine learning, visual perception, pattern recognition, in geographic analysis, cartography, biology, and many more. Our results can be divided into three groups.1. β-skeletons in L_p metrics. We present a parallel algorithm that for a set of n points needs O(log^2 n) time to construct β-skeleton for β є [1,2] in PRAM-CREW model with O(n) processors. We also describe two algorithms computing β-spectrum for β є [1,2]. β-spectrum is a labeling of edges, where with each edge e we associate the maximum value of β such that e belongs to the β-skeleton for this β. One of these algorithms is sequential, and for a set of n points requires O(n log^2n) time. The second algorithm requires O(log^4 n) time in parallel CREW-PRAM model with O(n) processors. We also describe how to transform algorithms in CREW-PRAM model so that they can be used in distributed models. Hence, we show that it is possible to get poly-logarithmic distributed algorithms for computing β-skeleton and β-spectrum for β є [1,2] in model with O(n) processors.2. β-skeletons for points moving along line segments. While researching β-skeletons in L_p metrics, we encountered a problem of computing the β-skeleton for a set of points, where each point can move along some fixed line segment. This motivated us to research β-skeletons for sets of line segments. We provide an algorithm that for β≥1 computes the circle-based β-skeleton for a set S of n segments in the Euclidean plane in O(n^2 α (n) log n) time, and for the same values of β it computes lune-based β-skeleton in O(n^2 λ_4(n)), where α is a functional inverse of the Ackermann’s function, and λ_4(n) denotes the maximum possible length of a (n,4) Davenport-Schinzel sequence. For 0 < β < 1, we prove that the β-skeleton can be constructed in a O(n^3 λ_4(n)) time. In the special case of β = 1, which is a generalization of Gabriel Graph, we present an algorithm that computes the β-skeleton in O(n log n) time. 3. β-skeletons for sets of weighted points.We introduce a new family of graphs. Specifically, we present a definition of weighted β-skeletons for a set of points with weights such that in a space with appropriate distance function the weighted β-skeletons for β ≥1 are subgraphs of the graph dual to the additively weighted Voronoi diagram. For a set of n weighted points we show that the weighted β-skeleton can be computed in O(n^{5/2}log^{1/2}n) time for β <1, and in O(n^{3/2}log^{1/2}n) time for β≥1. Next, we characterize β-skeletons for a set of weighted points in a space with power distance function. In this case the circle-based β-skeletons for β ≥ 1 are connected to the dual graph of the power diagram. Based on these results, we present a general, distance-based definition of β-skeletons that can be used in various metrics spaces, and not only for sets of points, but also for other types of objects. We also explore the connection between β-skeletons and γ-neighborhood graphs, and between β-skeletons and α-shapes.W tej rozprawie przedstawimy różne wyniki z naszych badań powiązanych z β-szkieletami. Definicja β-szkieletów została wprowadzona przez Kirpatricka i Radke. Należą one do rodziny grafów sąsiedztwa, grafów geometrycznych, gdzie dane dwa wierzchołki łączy krawędź wtedy i tylko wtedy, gdy spełniają one jakiś ustalony geometryczny warunek. Dla β-szkieletów taka krawędź istnieje między punktami v_1 i v_2, jeśli żaden punkt z ustalonego zbioru nie leży w obszarze nazywanym β-sąsiedztwem (odpowiednio, β-soczewką) v_1 i v_2. Ze względu na kształt tego obszaru rozróżniamy dwie rodziny β-szkieletów: β-szkielety soczewkowe i β-szkielety kołowe. β-szkielety znajdują zastosowania w różnych dziedzinach: w uczeniu maszynowym, percepcji wizualnej, w rozpoznawaniu wzorców, w analizie geograficznej, kartografii, biologii, i wielu innychNasze wyniki mogą być podzielone na trzy grupy. 1. β-szkielety w metrykach L_p. Przedstawiamy równoległy algorytm, który dla zbioru n punktów konstruuje β-szkielet dla βє [1,2] w czasie O(log^2 n) w modelu CREW-PRAM z O(n) procesorami. Opisujemy również dwa algorytmy obliczające β-spektrum dla β є [1,2], gdzie β-spektrum to przypisanie do każdej krawędzi takiej wartości parametru β, dla której krawędź ta należy do β-szkieletu. Jeden z nich jest sekwencyjny i dla zbioru n punktów działa w czasie O(nlog^2n). Drugi jest równoległy i wymaga czasu O(log^4n) w modelu CREW-PRAM z O(n) procesorami. Przedstawiamy również polilogarytmiczny algorytm rozproszony obliczający β-spektrum i β-szkielet dla β є [1,2] w modelu z O(n) procesorami.2. β-szkielety dla zbiorów punktów, które poruszają się wzdłuż odcinków.Badając β-szkielety w metrykach L_p natrafiliśmy na następujący problem. Chcemy policzyć β-szkielet dla zbioru punktów, z których każdy porusza się wzdłuż jakiegoś odcinka.By rozwiązać ten problem rozważamy β-szkielety dla zbiorów odcinków. Przedstawiamy algorytm, który dla β≥ 1 i dla zbioru n odcinków na płaszczyźnie euklidesowej oblicza β-szkielet kołowy w czasie O(n^2 α (n) log n), a β-szkielet soczewkowy w czasie O(n^2 λ_4(n)), gdzie α jest odwrotnością funkcji Ackermanna, a λ_4(n) oznacza maksymalną możliwą długość ciągu (n,4) Davenport'a-Schinzel'a. W przypadku β=1 przedstawiamy specjalny algorytm, który oblicza Graf Gabriela dla zbioru n odcinków w czasie O(nlog n). 3. β-szkielety dla zbiorów punktów z wagami.Prezentujemy również definicję ważonych β-szkieletów dla zbioru punktów z wagami. W przestrzeni z odpowiednią funkcją odległości te szkielety są dla β≥ 1 podgrafami grafu dualnego do addytywnie ważonego diagramu Voronoi. Przedstawiamy algorytm, który dla zbioru n punktów z wagami oblicza ważony β-szkielet w czasie O(n^{5/2}log^{1/2}n) dla β є [0,1] i w czasie O(n^{1/2}log^{1}/2}n) dla β≥1. Następnie definiujemy β-szkielety dla zbioru ważonych punktów w przestrzeni z odległością potęgową. W tym przypadku kołowe β-szkielety dla β≥ 1 są powiązane z grafem dualnym do diagramu potęgowego. Korzystając z tych wyników wprowadzamy uogólnioną definicję β-szkieletów opartą na odległościach pomiędzy punktami, którą można użyć w różnych przestrzeniach metrycznych, a także dla zbiorów obiektów innych niż punkty. Pokazujemy również związek pomiędzy β-szkieletami, a grafami γ-sąsiedztwa, oraz ten łączący β-szkielety i α-kształty.
Book chapters on the topic "Parametrized graphs"
1
Faran, Rachel, and Orna Kupferman. "A Parametrized Analysis of Algorithms on Hierarchical Graphs." In Descriptional Complexity of Formal Systems, 114–27. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-60252-3_9.
Full text
2
Marcilon, Thiago, and Rudini Sampaio. "The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results." In Graph-Theoretic Concepts in Computer Science, 169–85. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016. http://dx.doi.org/10.1007/978-3-662-53174-7_13.
Full text
3
Duff, Iain, and Florent Lopez. "Experiments with Sparse Cholesky Using a Parametrized Task Graph Implementation." In Parallel Processing and Applied Mathematics, 197–206. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-78024-5_18.
Full text
4
Agullo, Emmanuel, George Bosilca, Alfredo Buttari, Abdou Guermouche, and Florent Lopez. "Exploiting a Parametrized Task Graph Model for the Parallelization of a Sparse Direct Multifrontal Solver." In Euro-Par 2016: Parallel Processing Workshops, 175–86. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-58943-5_14.
Full textConference papers on the topic "Parametrized graphs"
1
Ferguson, Kevin, James Hardin, Andrew Gillman, and Levent Burak Kara. "Scalar Field Prediction on Topologically-Varying Graphs Using Spectral Shape Encoding." In ASME 2022 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2022. http://dx.doi.org/10.1115/detc2022-91209.
Full textAbstract:
Abstract Scalar fields, such as stress or temperature fields, are often calculated in shape optimization and design problems in engineering. For complex problems where shapes have varying topology and cannot be parametrized, data-driven scalar field prediction can be faster than traditional finite-element methods. However, current data-driven techniques to predict scalar fields are limited to a fixed grid domain, instead of arbitrary graph/mesh structures. In this work, we propose a method to predict scalar fields on meshes of arbitrary refinement and topology. It uses features that capture shape geometry on a local and global scale as input to a multilayer perceptron to predict solutions to partial differential equations on graph data structures. The proposed set of global features is a vector that concisely represents the entire mesh as a spectral shape encoding. The model is trained on finite-element von Mises stress fields, and once trained it can estimate stress values at each node on any input mesh. Two shape datasets are investigated, and the model demonstrates decent performance on both, with a median R-squared value of 0.75. We also demonstrate the model’s performance on a temperature field in a conduction problem, where its predictions have a median R-squared value of 0.98. By predicting from a simple, yet rich, set of mesh features, our method provides a potential flexible alternative to finite-element simulation in engineering design contexts. Code and datasets are available at: https://github.com/kevinferg/spectral-shape-encoding.
2
Camargo, Priscila, Alan D. A. Carneiro, and Uéverton S. Santos. "Complexidade Parametrizada de Cliques e Conjuntos Independentes em Grafos Prismas Complementares." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3166.
Full textAbstract:
The complementary prism GG¯ arises from the disjoint union of the graph G and its complement G¯ by adding the edges of a perfect matching joining pairs of corresponding vertices of G and G¯. The classical problems of graph theory, clique and independent set were proved NP-complete when the input graph is a complemantary prism. In this work, we study the complexity of both problems in complementary prisms graphs from the parameterized complexity point of view. First, we prove that these problems have a kernel and therefore are Fixed-Parameter Tractable (FPT). Then, we show that both problems do not admit polynomial kernel.
3
"SYNCHRONIZING USER INTERACTIONS WITH MULTIPLE PARAMETRIZED THREE-DIMENSIONAL WEB GRAPHICS." In International Conference on Computer Graphics Theory and Applications. SciTePress - Science and and Technology Publications, 2009. http://dx.doi.org/10.5220/0001773104010404.
Full text
4
Gama, Simone, Rosiane De Freitas, and Ueverton Souza. "Aspectos de complexidade parametrizada e problemas análogos em problemas de lista coloração de grafos e suas variações." In IV Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/etc.2019.6402.
Full textAbstract:
Lista-coloração é uma generalização do problema clássico de coloração de vértices em grafos. Tal problema possui algumas variações, dentre elas a coloração. Neste trabalho, uma redutibilidade do problema da lista coloração para a coloração e pré-coloração estendida é apresentada, para melhor se prover uma análise da coloração sob o enfoque da complexidade parametrizada, onde a mesma é FPT quando parametrizada pela cobertura de vértices e listas de cores. É apresentada também a prova de corretude de um algoritmo polinomial, dado na literatura, para coloração em grafos bipartidos completos.
5
Araújo, Rafael T., Sulamita Klein, and Rudini Sampaio. "Algoritmos FPT para reconhecer grafos bem cobertos." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3140.
Full textAbstract:
Dado um grafo G, sejam vc(G) e vc+(G) os tamanhos de uma cobertura mínima de vértices e de uma máxima cobertura minimal de vértices, respectivamente. Dizemos que G é bem coberto se vc(G) = vc+(G) (ou seja, todas as coberturas minimais são mínimas). É coNP-completo decidir se um grafo é bem coberto. Nesse artigo, obtemos algoritmos FPT de tempos O⇤ (2vc) e O⇤ (1.4656vc+) para decidir se um grafo é bem coberto, parametrizados por vc(G) e vc+(G), respectivamente, melhorando resultados de Boria et al. em 2015. Também obtemos algoritmo FPT parametrizado por ↵ (G) = n vc(G) em grafos d-degenerados, que inclui grafos com genus limitado (como grafos planares) e grafos com grau máximo limitado. Finalmente usamos a decomposição primeval para obter algoritmo linear para grafos P4-laden estendidos e grafos (q, q 4), que é FPT parametrizado por q, melhorando resultados de Klein et al. em 2013.
6
Araújo, Júlio, Alexandre Cezar, Carlos V. G. C. Lima, Vinicius F. dos Santos, and Ana Silva. "Sobre o Número de Orientação Própria de Grafos Cordais." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/etc.2021.16384.
Full textAbstract:
Uma orientação $D$ de um grafo simples $G=(V,E)$ é própria se os vértices~$u$ e~$v$ possuem graus de entrada distintos, sempre que~$uv \in E$. O número de orientação de um grafo $G$ é o menor inteiro positivo $k$ tal que $G$ tem uma orientação própria $D$ com maior grau de entrada igual a $k$, denotado por $\po(G)$. Mostramos que decidir se $\po(G) \le k$ é~\FPT, parametrizado por $k$, quando restrito a grafos cordais, apresentamos um kernel exponencial para esta classe de grafos e mostramos que não existe kernel polinomial a menos que $\NP \subseteq \coNP/\poly$. Apresentamos também kernels melhores para grafos split e cobipartidos. Além disto, apresentamos limitantes para subclasses de grafos cordais como grafos blocos, periplanares cordais e para cografos.
7
Lemos, Anderson, Vinicius F. Dos Santos, and Olga Goussevskaia. "Seleção de Representantes para Cobertura de Componentes Conexas em Grafos." In XXXII Concurso de Teses e Dissertações da SBC. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/ctd.2019.6339.
Full textAbstract:
Introduzimos um novo problema de cobertura chamado Cobertura de Componentes por Vértices (CCV). Neste problema são dados um grafo G e uma partição A e B de V(G), e nosso objetivo ´e encontrar o menor subconjunto B de B tal que, para cada componente conexa C de G[A], há um vértice v ∈ C com algum vizinho em B?. Estudamos a complexidade deste problema e damos resultados positivos e negativos. Mostramos que o problema CCV e NP- Completo para várias classes de grafos. Mostramos tamb´em que o problema é difícil de aproximar e de parametrizar. Por outro lado, apresentamos algoritmos polinomiais para outras classes de grafos. Por fim, mostramos parametrizações FPT e algoritmos aproximativos para determinadas classes de grafos.
8
Costa, Diego Rangel Piranga, Vinicius Fernandes dos Santos, and Phablo F. S. Moura. "Problemas de Particionamento de Grafos em Árvores Monocromáticas." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2022. http://dx.doi.org/10.5753/etc.2022.223189.
Full textAbstract:
Problemas de partição de grafos é uma importante classe de problemas de grafos que são capazes de modelar tarefas do mundo real, como, alocação concorrente de processadores e integração de sistemas de larga escala (VLSI). Mesmo tais problemas sendo NP-difíceis, existe muito esforço em desenvolver métodos para tratar tais problemas. Neste trabalho apresentamos resultados do ponto de vista de complexidade computacional para o Problema de Partição de Grafos em Árvores Monocromáticas conhecido como PGMT, onde demonstramos a NP-dificuldade mesmo para versões restritas do problema. Além disso, apresentamos um limitante inferior para o tempo de execução de algoritmos baseados na Hipótese do Tempo Exponencial (ETH) e também apresentamos dois algoritmos, um baseado em programação dinâmica quando consideramos que o grafo da entrada é uma árvore e um outro algoritmo parametrizado pela largura arbórea e pelo número de cores.
9
Wang, J. Y., and J. K. Wu. "A Computational Environment for Dextrous Workspace Analysis." In ASME 1992 Design Technical Conferences. American Society of Mechanical Engineers, 1992. http://dx.doi.org/10.1115/detc1992-0178.
Full textAbstract:
Abstract This paper presents an interactive engineering environment for dextrous workspace analysis of manipulators. The environment contains a mechanical system modeling tool, an automatic differentiation package, and numerical solvers that map one-dimensional and two-dimensional solution sets of nonlinear parametrized kinematic constraint equations. Row-rank deficiency of constraint sub-Jacobian matrices is used as a necessary condition for characterizing the boundaries of the workspaces and dextrous workspaces of manipulators. A cursor driven animation capability, developed in an interactive graphics environment allows the user to retrieve system configurations by dragging the cursor along solution branches. An animation of the assembled configuration along that solution branch is then displayed. Thus, a better understanding of the kinematic behavior of mechanical systems that limits their dexterity can be obtained. A construction backhoe mechanical system is used to demonstrate the capability of the method developed.
10
Mongelli, Henrique, and Rodrigo Cesar Sakamoto. "Implementações de Algoritmos Paralelos FPT para o Problema da k-Cobertura por Vértices utilizando Clusters e Grades Computacionais." In Workshop em Sistemas Computacionais de Alto Desempenho. Sociedade Brasileira de Computação, 2007. http://dx.doi.org/10.5753/wscad.2007.18764.
Full textAbstract:
Em muitas aplicações problemas NP-completos precisam ser solucionados de forma exata. Um método promissor para tratar com alguns problemas intratáveis é através da Complexidade Parametrizada que divide a entrada do problema em uma parte principal e um parâmetro. A parte principal contribui polinomialmente com a complexidade total do problema, enquanto que o parâmetro é responsável pela explosão combinatorial. Consideramos o algoritmo paralelo FPT de Cheetham para solucionar o problema da k-Cobertura por Vértices e a implementação refinada e melhorada de Hanashiro. Como este é um problema em que grande parte do tempo de execução é feita de forma independente, sem a necessidade de comunicação entre os processadores, a utilização de grades computacionais torna-se bastante aplicável, com a possibilidade do emprego de um número grande de processadores. Este trabalho envolve a implementação no Integrade de algoritmos FPT paralelos para o problema da k-Cobertura por vértices. A grade computacional dos testes utiliza o middleware desenvolvido no Projeto Integrade. Estes algoritmos foram implementados usando a biblioteca BSPLib do Integrade e mostraram um desempenho muito bom e que pode ser melhorado com a adição de novos processadores. Em nossos experimentos no Integrade, em comparação a implementação em cluster, obtivemos tempos paralelos melhores do que os relatados por Hanashiro.