Journal articles: '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 text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

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 text

APA, Harvard, Vancouver, ISO, and other styles

11

NASTOS, JAMES, and YONG GAO. "BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES." Discrete Mathematics, Algorithms and Applications 04, no. 01 (March 2012): 1250008. http://dx.doi.org/10.1142/s1793830912500085.

Full text

Abstract:

Many fixed-parameter tractable algorithms using a bounded search tree have been repeatedly improved, often by describing a larger number of branching rules involving an increasingly complex case analysis. We introduce a novel and general search strategy that branches on the forbidden subgraphs of a graph class relaxation. By using the class of P4-sparse graphs as the relaxed graph class, we obtain efficient bounded search tree algorithms for several parametrized deletion problems. We give the first non-trivial bounded search tree algorithms for the cograph edge-deletion problem and the trivially perfect edge-deletion problems. For the cograph vertex deletion problem, a refined analysis of the runtime of our simple bounded search algorithm gives a faster exponential factor than those algorithms designed with the help of complicated case distinctions and non-trivial running time analysis [R. Niedermeier and P. Rossmanith, An efficient fixed-parameter algorithm for 3-hitting set, J. Discrete Algorithms1(1) (2003) 89–102] and computer-aided branching rules [J. Gramm, J. Guo, F. Hüffner and R. Niedermeier, Automated generation of search tree algorithms for hard graph modification problems, Algorithmica39(4) (2004) 321–347].

APA, Harvard, Vancouver, ISO, and other styles

12

Blum, Johannes, Stefan Funke, and Sabine Storandt. "Sublinear search spaces for shortest path planning in grid and road networks." Journal of Combinatorial Optimization 42, no. 2 (July 29, 2021): 231–57. http://dx.doi.org/10.1007/s10878-021-00777-3.

Full text

Abstract:

AbstractShortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in, e.g., road or grid networks is an important challenge. The most successful techniques for fast query answering rely on preprocessing. However, for many of these techniques it is not fully understood why they perform so remarkably well, and theoretical justification for the empirical results is missing. An attempt to explain the excellent practical performance of preprocessing based techniques on road networks (as transit nodes, hub labels, or contraction hierarchies) in a sound theoretical way are parametrized analyses, e.g., considering the highway dimension or skeleton dimension of a graph. Still, these parameters may be large in case the network contains grid-like substructures—which inarguably is the case for real-world road networks around the globe. In this paper, we use the very intuitive notion of bounded growth graphs to describe road networks and also grid graphs. We show that this model suffices to prove sublinear search spaces for the three above mentioned state-of-the-art shortest path planning techniques. Furthermore, our preprocessing methods are close to the ones used in practice and only require expected polynomial time.

APA, Harvard, Vancouver, ISO, and other styles

13

DEPRETTERE, ED F., PETER HELD, and PAUL WIELAGE. "MODEL AND METHODS FOR REGULAR ARRAY DESIGN." International Journal of High Speed Electronics and Systems 04, no. 02 (June 1993): 133–201. http://dx.doi.org/10.1142/s012915649300008x.

Full text

Abstract:

We present a unified framework for the transformation of algorithms to architectures in the domains of high speed signal and algebraic processing. The framework starts from algorithmic specifications in a language suited for numerical analysis (such as Matlab), transforms the high level description into hierarchical and structured data flow dependence graphs, allows the designer to manipulate the graphs, to merge them, abstract them, regularize them, cluster and partition them etc… until the description of an architecture which can represent the hardware in a precise manner is obtained. A generic model for hierarchical, parametrized descriptions assures a consistent design methodology throughout. In the process, we not only generate attractive parallel architectures based on a fixed array of processing elements, but also their control and the program that has to be executed by the host processor. Because of the parametrization, the designs are "generic" and hence reusable, but they are restricted to cases where the parameters are known at "generation time".

APA, Harvard, Vancouver, ISO, and other styles

14

SITHARAM, MEERA, YONG ZHOU, and JÖRG PETERS. "RECONCILING CONFLICTING COMBINATORIAL PREPROCESSORS FOR GEOMETRIC CONSTRAINT SYSTEMS." International Journal of Computational Geometry & Applications 20, no. 06 (December 2010): 631–51. http://dx.doi.org/10.1142/s0218195910003463.

Full text

Abstract:

Polynomial equation systems arising from real applications often have associated combinatorial information, expressible as graphs and underlying matroids. To simplify the system and improve its numerical robustness before attempting to solve it with numeric-algebraic techniques, solvers can employ graph algorithms to extract substructures satisfying or optimizing various combinatorial properties. When there are underlying matroids, these algorithms can be greedy and efficient. In practice, correct and effective merging of the outputs of different graph algorithms to simultaneously satisfy their goals is a key challenge. This paper merges and improves two highly effective but separate graph-based algorithms that preprocess systems for resolving the relative position and orientation of a collection of incident rigid bodies. Such collections naturally arise in many situations, for example in the recombination of decomposed large geometric constraint systems. Each algorithm selects a subset of incidences, one to optimize algebraic complexity of a parametrized system, the other to obtain a well-formed system that is robust against numerical errors. Both algorithms are greedy and can be proven correct by revealing underlying matroids. The challenge is that the output of the first algorithm is not guaranteed to be extensible to a well-formed system, while the output of the second may not have optimal algebraic complexity. Here we show how to reconcile the two algorithms by revealing well-behaved maps between the associated matroids.

APA, Harvard, Vancouver, ISO, and other styles

15

Zhang, Kewei, Antonio Orlando, and Elaine Crooks. "Compensated convexity and Hausdorff stable geometric singularity extractions." Mathematical Models and Methods in Applied Sciences 25, no. 04 (January 19, 2015): 747–801. http://dx.doi.org/10.1142/s0218202515500189.

Full text

Abstract:

We develop and apply the theory of lower and upper compensated convex transforms introduced in [K. Zhang, Compensated convexity and its applications, Ann. Inst. H. Poincaré Anal. Non Linéaire 25 (2008) 743–771] to define multiscale, parametrized, geometric singularity extraction transforms of ridges, valleys and edges of function graphs and sets in ℝn. These transforms can be interpreted as "tight" opening and closing operators, respectively, with quadratic structuring functions. We show that these geometric morphological operators are invariant with respect to translation, and stable under curvature perturbations, and establish precise locality and tight approximation properties for compensated convex transforms applied to bounded functions and continuous functions. Furthermore, we establish multiscale and Hausdorff stable versions of such transforms. Specifically, the stable ridge transforms can be used to extract exterior corners of domains defined by their characteristic functions. Examples of explicitly calculated prototype mathematical models are given, as well as some numerical experiments illustrating the application of these transforms to 2d and 3d objects.

APA, Harvard, Vancouver, ISO, and other styles

16

EIDENBENZ, S., A. Å. HANSSON, V. RAMASWAMY, and C. M. REIDYS. "ON A NEW CLASS OF LOAD BALANCING NETWORK PROTOCOLS." Advances in Complex Systems 10, no. 03 (September 2007): 359–77. http://dx.doi.org/10.1142/s0219525907001148.

Full text

Abstract:

In this paper we study a new class of generic, parametrized, locally load-sensing (LLS) network-routing protocols over simple graphs, Y. These protocols are Y-"local" in the sense that they transmit packets only between Y-adjacent vertices and LLS since they base their "routing decisions" dynamically on queue-sizes of their neighbors and their relative distance to the destination. In the system each vertex has specific data-queues indexed by its respective Y-neighbors. The state of a vertex then consists of the collection of queue-sizes. The data-transmission protocols are formally specified in the framework of sequential dynamical systems, which allows us to categorize and classify our experiments. We will investigate the following scenario: for fixed Y we assume a single source/destination pair to be given and a system-update then consists of the collection of local protocol updates according to some fixed permutation of the Y-vertices. We then iterate the system-updates and thereby obtain the time evolution of the queue-sizes of the vertices. We will present and discuss results on the evolution of the load, i.e. the total number of packets in the network, the throughput, i.e. the rate at which packets arrive at the destination, and study the dependence of the queue-size dynamics on various other system parameters. In particular, we will analyze update schedule dependency and the impact of queue-capacity on system stability. We will show that our protocols can adapt and dynamically utilize new routes in a fixed network.

APA, Harvard, Vancouver, ISO, and other styles

17

Montenegro, Marcelo, and Sebastián Lorca. "Height estimates for graph parametrized surfaces." Bulletin des Sciences Mathématiques 136, no. 8 (December 2012): 848–56. http://dx.doi.org/10.1016/j.bulsci.2012.07.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

de Oliveira Guimarães, José. "Parametrized methods." ACM SIGPLAN Notices 28, no. 11 (November 1993): 28–32. http://dx.doi.org/10.1145/165564.165572.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

McCarthy, P. J., M. Crampin, and W. Stephenson. "Graphs in the plane invariant under an area preserving linear map and general continuous solutions of certain quadratic functional equations." Mathematical Proceedings of the Cambridge Philosophical Society 97, no. 2 (March 1985): 261–78. http://dx.doi.org/10.1017/s0305004100062812.

Full text

Abstract:

AbstractThe requirement that the graph of a function be invariant under a linear map is equivalent to a functional equation of f. For area preserving maps M(det (M) = 1), the functional equation is equivalent to an (easily solved) linear one, or to a quadratic one of the formfor all Here 2C = Trace (M). It is shown that (Q) admits continuous solutions ⇔ M has real eigenvalues ⇔ (Q) has linear solutions f(x) = λx ⇔ |C| ≥ 1. For |c| = 1 or C < – 1, (Q) only admits a few simple solutions. For C > 1, (Q) admits a rich supply of continuous solutions. These are parametrised by an arbitrary function, and described in the sense that a construction is given for the graphs of the functions which solve (Q).

APA, Harvard, Vancouver, ISO, and other styles

20

Szocinski, Timothy, Duc Duy Nguyen, and Guo-Wei Wei. "AweGNN: Auto-parametrized weighted element-specific graph neural networks for molecules." Computers in Biology and Medicine 134 (July 2021): 104460. http://dx.doi.org/10.1016/j.compbiomed.2021.104460.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Jenei, Márk, and James A. Elliott. "Substitution effect in the graph model of polymerisation parametrised by atomistic simulations." Computational Materials Science 208 (June 2022): 111315. http://dx.doi.org/10.1016/j.commatsci.2022.111315.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Farin, Gerald. "Rational quadratic circles are parametrized by chord length." Computer Aided Geometric Design 23, no. 9 (December 2006): 722–24. http://dx.doi.org/10.1016/j.cagd.2006.08.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Jeong, Moon-Hwan, and Hyeong-Seok Ko. "Draft-space warping: grading of clothes based on parametrized draft." Computer Animation and Virtual Worlds 24, no. 3-4 (May 2013): 377–86. http://dx.doi.org/10.1002/cav.1503.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Wang, F. C., P. K. Wright, B. A. Barsky, and D. C. H. Yang. "Approximately Arc-Length Parametrized C3 Quintic Interpolatory Splines." Journal of Mechanical Design 121, no. 3 (September 1, 1999): 430–39. http://dx.doi.org/10.1115/1.2829479.

Full text

Abstract:

A quasi-global interpolation method that fits a quintic spline curve to a set of designated data points is described in this paper. The resultant curve has several important features. First, the curve is smooth with C3 continuity and has no unwanted oscillations. Second, the generated quintic spline is “optimally” parametrized; that is, the curve is parametrized very closely to its arc length. In addition, with the interpolation method, straight line segments can be preserved to generate a quintic spline of hybrid curve segments. The properties of C3 continuity and the “near arc length” parametrization have direct applications to trajectory planning in robotics and the development of new types of machine tool controllers for high speed and precision machining. The encapsulation of straight line segments enhances the capability for the shape designers to design more complicated shapes, including free form curves and straight line segments in a uniform way.

APA, Harvard, Vancouver, ISO, and other styles

25

BELL, MARK C., VALENTINA DISARLO, and ROBERT TANG. "Cubical geometry in the polygonalisation complex." Mathematical Proceedings of the Cambridge Philosophical Society 167, no. 01 (May 8, 2018): 1–22. http://dx.doi.org/10.1017/s0305004118000130.

Full text

Abstract:

AbstractWe introduce the polygonalisation complex of a surface, a cube complex whose vertices correspond to polygonalisations. This is a geometric model for the mapping class group and it is motivated by works of Harer, Mosher and Penner. Using properties of the flip graph, we show that the midcubes in the polygonalisation complex can be extended to a family of embedded and separating hyperplanes, parametrised by the arcs in the surface.We study the crossing graph of these hyperplanes and prove that it is quasi-isometric to the arc complex. We use the crossing graph to prove that, generically, different surfaces have different polygonalisation complexes. The polygonalisation complex is not CAT(0), but we can characterise the vertices where Gromov's link condition fails. This gives a tool for proving that, generically, the automorphism group of the polygonalisation complex is the (extended) mapping class group of the surface.

APA, Harvard, Vancouver, ISO, and other styles

26

Barber, David. "Identifying graph clusters using variational inference and links to covariance parametrization." Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 367, no. 1906 (November 13, 2009): 4407–26. http://dx.doi.org/10.1098/rsta.2009.0117.

Full text

Abstract:

Finding clusters of well-connected nodes in a graph is a problem common to many domains, including social networks, the Internet and bioinformatics. From a computational viewpoint, finding these clusters or graph communities is a difficult problem. We use a clique matrix decomposition based on a statistical description that encourages clusters to be well connected and few in number. The formal intractability of inferring the clusters is addressed using a variational approximation inspired by mean-field theories in statistical mechanics. Clique matrices also play a natural role in parametrizing positive definite matrices under zero constraints on elements of the matrix. We show that clique matrices can parametrize all positive definite matrices restricted according to a decomposable graph and form a structured factor analysis approximation in the non-decomposable case. Extensions to conjugate Bayesian covariance priors and more general non-Gaussian independence models are briefly discussed.

APA, Harvard, Vancouver, ISO, and other styles

27

Narváez, David E. "A QSAT Benchmark Based on Vertex-Folkman Problems (Student Abstract)." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 10 (April 3, 2020): 13881–82. http://dx.doi.org/10.1609/aaai.v34i10.7213.

Full text

Abstract:

The purpose of this paper is to draw attention to a particular family of quantified Boolean formulas (QBFs) stemming from encodings of some vertex Folkman problems in extremal graph theory. We argue that this family of formulas is interesting for QSAT research because it is both conceptually simple and parametrized in a way that allows for a fine-grained diversity in the level of difficulty of its instances. Additionally, when coupled with symmetry breaking, the formulas in this family exhibit backbones (unique satisfying assignments) at the top-level existential variables. This benchmark is thus suitable for addressing questions regarding the connection between the existence of backbones and the hardness of QBFs.

APA, Harvard, Vancouver, ISO, and other styles

28

BIELECKI, WLODZIMIERZ, TOMASZ KLIMEK, MAREK PALKOWSKI, and ANNA BELETSKA. "AN ITERATIVE ALGORITHM OF COMPUTING THE TRANSITIVE CLOSURE OF A UNION OF PARAMETRIZED AFFINE INTEGER TUPLE RELATIONS." Discrete Mathematics, Algorithms and Applications 04, no. 01 (March 2012): 1250011. http://dx.doi.org/10.1142/s1793830912500115.

Full text

Abstract:

A novel iterative algorithm of calculating the exact transitive closure of a parametrized graph being represented by a union of simple affine integer tuple relations is presented. When it is not possible to calculate exact transitive closure, the algorithm produces its upper bound. To calculate the transitive closure of the union of all simple relations, the algorithm recognizes the class of each simple relations, calculates its exact transitive closure, forms the union of calculated transitive closures, and applies this union in an iterative procedure. Results of experiments aimed at the comparison of the effectiveness of the presented algorithm with those of related ones are outlined and discussed.

APA, Harvard, Vancouver, ISO, and other styles

29

BOWLIN, GARRY, and MATTHEW G. BRIN. "COLORING PLANAR GRAPHS VIA COLORED PATHS IN THE ASSOCIAHEDRA." International Journal of Algebra and Computation 23, no. 06 (September 2013): 1337–418. http://dx.doi.org/10.1142/s0218196713500276.

Full text

Abstract:

Hassler Whitney's theorem of 1931 reduces the task of finding proper, vertex 4-colorings of triangulations of the 2-sphere to finding such colorings for the class ℌ of triangulations of the 2-sphere that have a Hamiltonian circuit. This has been used by Whitney and others from 1936 to the present to find equivalent reformulations of the 4 Color Theorem (4CT). Recently there has been activity to try to use some of these reformulations to find a shorter proof of the 4CT. Every triangulation in ℌ has a dual graph that is a union of two binary trees with the same number of leaves. Elements of a group known as Thompson's group F are equivalence classes of pairs of binary trees with the same number of leaves. This paper explores this resemblance and finds that some recent reformulations of the 4CT are essentially attempting to color elements of ℌ using expressions of elements of F as words in a certain generating set for F. From this, we derive information about not just the colorability of certain elements of ℌ, but also about all possible ways to color these elements. Because of this we raise (and answer some) questions about enumeration. We also bring in an extension E of the group F and ask whether certain elements "parametrize" the set of all colorings of the elements of ℌ that use all four colors.

APA, Harvard, Vancouver, ISO, and other styles

30

Rakowska, J., R. T. Haftka, and L. T. Watson. "An active set algorithm for tracing parametrized optima." Structural Optimization 3, no. 1 (March 1991): 29–44. http://dx.doi.org/10.1007/bf01743487.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

WATANABE, Y., and K. FUKUMIZU. "New Graph Polynomials from the Bethe Approximation of the Ising Partition Function." Combinatorics, Probability and Computing 20, no. 2 (June 30, 2010): 299–320. http://dx.doi.org/10.1017/s0963548310000258.

Full text

Abstract:

We introduce two graph polynomials and discuss their properties. One is a polynomial of two variables whose investigation is motivated by the performance analysis of the Bethe approximation of the Ising partition function. The other is a polynomial of one variable that is obtained by the specialization of the first one. It is shown that these polynomials satisfy deletion–contraction relations and are new examples of the V-function, which was introduced by Tutte (Proc. Cambridge Philos. Soc.43, 1947, p. 26). For these polynomials, we discuss the interpretations of special values and then obtain the bound on the number of sub-coregraphs,i.e., spanning subgraphs with no vertices of degree one. It is proved that the polynomial of one variable is equal to the monomer–dimer partition function with weights parametrized by that variable. The properties of the coefficients and the possible region of zeros are also discussed for this polynomial.

APA, Harvard, Vancouver, ISO, and other styles

32

van Emmerik, Maarten J. G. M. "Creation and modification of parametrized solid models by graphical interaction." Computers & Graphics 13, no. 1 (January 1989): 71–76. http://dx.doi.org/10.1016/0097-8493(89)90041-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

FISH, JOEL W. "ESTIMATES FOR J-CURVES AS SUBMANIFOLDS." International Journal of Mathematics 22, no. 10 (October 2011): 1375–431. http://dx.doi.org/10.1142/s0129167x11007306.

Full text

Abstract:

In this paper, we develop some basic analytic tools to study compactness properties of J-curves (i.e. pseudoholomorphic curves) when regarded as submanifolds. Incorporating techniques from the theory of minimal surfaces, we derive an inhomogeneous mean curvature equation for such curves by establishing an extrinsic monotonicity principle for nonnegative functions f satisfying Δf ≥ -c2f, we show that curves locally parametrized as a graph over a coordinate tangent plane have all derivatives a priori bounded in terms of curvature and ambient geometry, and we thus establish ϵ-regularity for the square length of their second fundamental forms. These results are all provided for J-curves either with or without Lagrangian boundary and hold in almost all Hermitian manifolds of arbitrary even dimension (i.e. Riemannian manifolds for which the almost complex structure is an isometry).

APA, Harvard, Vancouver, ISO, and other styles

34

GRAFFI, SANDRO, and LORENZO ZANELLI. "GEOMETRIC APPROACH TO THE HAMILTON–JACOBI EQUATION AND GLOBAL PARAMETRICES FOR THE SCHRÖDINGER PROPAGATOR." Reviews in Mathematical Physics 23, no. 09 (October 2011): 969–1008. http://dx.doi.org/10.1142/s0129055x11004497.

Full text

Abstract:

We construct a family of global Fourier Integral Operators, defined for arbitrary large times, representing a global parametrix for the Schrödinger propagator when the potential is quadratic at infinity. This construction is based on the geometric approach to the corresponding Hamilton–Jacobi equation and thus sidesteps the problem of the caustics generated by the classical flow. Moreover, a detailed study of the real phase function allows us to recover a WKB semiclassical approximation which necessarily involves the multivaluedness of the graph of the Hamiltonian flow past the caustics.

APA, Harvard, Vancouver, ISO, and other styles

35

Albert, Michael, and Vincent Vatter. "An Elementary Proof of Bevan's Theorem on the Growth of Grid Classes of Permutations." Proceedings of the Edinburgh Mathematical Society 62, no. 4 (March 11, 2019): 975–84. http://dx.doi.org/10.1017/s0013091519000026.

Full text

Abstract:

AbstractBevan established that the growth rate of a monotone grid class of permutations is equal to the square of the spectral radius of a related bipartite graph. We give an elementary and self-contained proof of a generalization of this result using only Stirling's formula, the method of Lagrange multipliers, and the singular value decomposition of matrices. Our proof relies on showing that the maximum over the space of n × n matrices with non-negative entries summing to one of a certain function of those entries, parametrized by the entries of another matrix Γ of non-negative real numbers, is equal to the square of the largest singular value of Γ and that the maximizing point can be expressed as a Hadamard product of Γ with the tensor product of singular vectors for its greatest singular value.

APA, Harvard, Vancouver, ISO, and other styles

36

Zhuang, Chungang, Zhenhua Xiong, and Han Ding. "Temperature-constrained topology optimization of nonlinear heat conduction problems." Journal of Computational Design and Engineering 8, no. 4 (June 18, 2021): 1059–81. http://dx.doi.org/10.1093/jcde/qwab032.

Full text

Abstract:

Abstract This paper presents topology optimization of nonlinear heat conduction problems with multiple domains and multiple constraints, including regional temperature and material volume for reducing temperature. Maximum approximation temperatures in the constraint regions are accurately and dynamically calculated, though temperature and temperature-dependent thermal conductivity change with the update of material distribution. A temperature measure with constant error to approximate regional maximum temperature is adaptive to different temperature ranges. A strategy of hole nucleation generation combined with the regional temperature constraints is presented for the level set-based topology optimization. The solid isotropic material with penalization (SIMP) and parametrized level set methods are compared for the temperature-constrained topology optimization. Finally, several numerical examples are solved by the SIMP and parametrized level set methods. The results demonstrate that the proposed approach can obtain intricate topological details and reduce regional temperatures for the nonlinear heat conduction problems.

APA, Harvard, Vancouver, ISO, and other styles

37

Savický, Petr, and Petr Kučera. "Generating Models of a Matched Formula With a Polynomial Delay." Journal of Artificial Intelligence Research 56 (June 29, 2016): 379–402. http://dx.doi.org/10.1613/jair.4989.

Full text

Abstract:

A matched formula is a CNF formula whose incidence graph admits a matching which matches a distinct variable to every clause. Such a formula is always satisfiable. Matched formulas are used, for example, in the area of parametrized complexity. We prove that the problem of counting the number of the models (satisfying assignments) of a matched formula is #P-complete. On the other hand, we define a class of formulas generalizing the matched formulas and prove that for a formula in this class one can choose in polynomial time a variable suitable for splitting the tree for the search of the models of the formula. As a consequence, the models of a formula from this class, in particular of any matched formula, can be generated sequentially with a delay polynomial in the size of the input. On the other hand, we prove that this task cannot be performed efficiently for linearly satisfiable formulas, which is a generalization of matched formulas containing the class considered above.

APA, Harvard, Vancouver, ISO, and other styles

38

Pitler, Emily. "A Crossing-Sensitive Third-Order Factorization for Dependency Parsing." Transactions of the Association for Computational Linguistics 2 (December 2014): 41–54. http://dx.doi.org/10.1162/tacl_a_00164.

Full text

Abstract:

Parsers that parametrize over wider scopes are generally more accurate than edge-factored models. For graph-based non-projective parsers, wider factorizations have so far implied large increases in the computational complexity of the parsing problem. This paper introduces a “crossing-sensitive” generalization of a third-order factorization that trades off complexity in the model structure (i.e., scoring with features over multiple edges) with complexity in the output structure (i.e., producing crossing edges). Under this model, the optimal 1-Endpoint-Crossing tree can be found in O( n4) time, matching the asymptotic run-time of both the third-order projective parser and the edge-factored 1-Endpoint-Crossing parser. The crossing-sensitive third-order parser is significantly more accurate than the third-order projective parser under many experimental settings and significantly less accurate on none.

APA, Harvard, Vancouver, ISO, and other styles

39

Pérez-Díaz, Sonia, and Li-Yong Shen. "Inversion, degree, reparametrization and implicitization of improperly parametrized planar curves using μ-basis." Computer Aided Geometric Design 84 (January 2021): 101957. http://dx.doi.org/10.1016/j.cagd.2021.101957.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Prasad, J., and A. R. Diaz. "Synthesis of Bistable Periodic Structures Using Topology Optimization and a Genetic Algorithm." Journal of Mechanical Design 128, no. 6 (December 28, 2005): 1298–306. http://dx.doi.org/10.1115/1.2338576.

Full text

Abstract:

A formulation for the automatic synthesis of two-dimensional bistable, compliant periodic structures is presented, based on standard methods for topology optimization. The design space is parametrized using nonlinear beam elements and a ground structure approach. A performance criterion is suggested, based on characteristics of the load-deformation curve of the compliant structure. A genetic algorithm is used to find candidate solutions. A numerical implementation of this methodology is discussed and illustrated using simple examples.

APA, Harvard, Vancouver, ISO, and other styles

41

Kosina, H., and C. Troger. "SPIN – A Schrödinger-Poisson Solver Including Nonparabolic Bands." VLSI Design 8, no. 1-4 (January 1, 1998): 489–93. http://dx.doi.org/10.1155/1998/39231.

Full text

Abstract:

Nonparabolicity effects in two-dimensional electron systems are quantitatively analyzed. A formalism has been developed which allows to incorporate a nonparabolic bulk dispersion relation into the Schrödinger equation. As a consequence of nonparabolicity the wave functions depend on the in-plane momentum. Each subband is parametrized by its energy, effective mass and a subband nonparabolicity coefficient. The formalism is implemented in a one-dimensional Schrödinger-Poisson solver which is applicable both to silicon inversion layers and heterostructures.

APA, Harvard, Vancouver, ISO, and other styles

42

Mühlherr, Bernhard, and Richard M. Weiss. "Tits Triangles." Canadian Mathematical Bulletin 62, no. 3 (November 15, 2018): 583–601. http://dx.doi.org/10.4153/s0008439518000140.

Full text

Abstract:

AbstractA Tits polygon is a bipartite graph in which the neighborhood of every vertex is endowed with an “opposition relation” satisfying certain properties. Moufang polygons are precisely the Tits polygons in which these opposition relations are all trivial. There is a standard construction that produces a Tits polygon whose opposition relations are not all trivial from an arbitrary pair $(\unicode[STIX]{x1D6E5},T)$, where $\unicode[STIX]{x1D6E5}$ is a building of type $\unicode[STIX]{x1D6F1}$, $\unicode[STIX]{x1D6F1}$ is a spherical, irreducible Coxeter diagram of rank at least $3$, and $T$ is a Tits index of absolute type $\unicode[STIX]{x1D6F1}$ and relative rank $2$. A Tits polygon is called $k$-plump if its opposition relations satisfy a mild condition that is satisfied by all Tits triangles coming from a pair $(\unicode[STIX]{x1D6E5},T)$ such that every panel of $\unicode[STIX]{x1D6E5}$ has at least $k+1$ chambers. We show that a $5$-plump Tits triangle is parametrized and uniquely determined by a ring $R$ that is alternative and of stable rank $2$. We use the connection between Tits triangles and the theory of Veldkamp planes as developed by Veldkamp and Faulkner to show existence.

APA, Harvard, Vancouver, ISO, and other styles

43

CAPPELLO, PETER, and ÖMER EĞECIOĞLU. "PROCESSOR LOWER BOUND FORMULAS FOR ARRAY COMPUTATIONS AND PARAMETRIC DIOPHANTINE SYSTEMS." International Journal of Foundations of Computer Science 09, no. 04 (December 1998): 351–75. http://dx.doi.org/10.1142/s0129054198000295.

Full text

Abstract:

Using a directed acyclic graph (dag) model of algorithms, we solve a problem related to precedence-constrained multiprocessor schedules for array computations: Given a sequence of dags and linear schedules parametrized by n, compute a lower bound on the number of processors required by the schedule as a function of n. In our formulation, the number of tasks that are scheduled for execution during any fixed time step is the number of non-negative integer solutions dn to a set of parametric linear Diophantine equations. We present an algorithm based on generating functions for constructing a formula for these numbers dn. The algorithm has been implemented as a Mathematica program. Example runs and the symbolic formulas for processor lower bounds automatically produced by the algorithm for Matrix-Vector Product, Triangular Matrix Product, and Gaussian Elimination problems are presented. Our approach actually solves the following more general problem: Given an arbitrary r× s integral matrix A and r-dimensional integral vectors b and c, let dn(n=0,1,…) be the number of solutions in non-negative integers to the system Az=nb+c. Calculate the (rational) generating function ∑n≥ 0dntn and construct a formula for dn.

APA, Harvard, Vancouver, ISO, and other styles

44

Shah, Nirav Vasant, Michele Girfoglio, Peregrina Quintela, Gianluigi Rozza, Alejandro Lengomin, Francesco Ballarin, and Patricia Barral. "Finite element based Model Order Reduction for parametrized one-way coupled steady state linear thermo-mechanical problems." Finite Elements in Analysis and Design 212 (December 2022): 103837. http://dx.doi.org/10.1016/j.finel.2022.103837.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Izumi, Masaki, Scott Morrison, and David Penneys. "Quotients of A2 * T2." Canadian Journal of Mathematics 68, no. 5 (October 1, 2016): 999–1022. http://dx.doi.org/10.4153/cjm-2015-017-4.

Full text

Abstract:

AbstractWe study unitary quotients of the free product unitary pivotal category A2 * T2. We show that such quotients are parametrized by an integer n ≥ 1 and an 2n–th root of unity ω. We show that for n = 1, 2, 3, there is exactly one quotient and ω = 1. For 4 ≤ n ≤ 10, we show that there are no such quotients. Our methods also apply to quotients of T2 * T2, where we have a similar result.The essence of our method is a consistency check on jellyfish relations. While we only treat the specific cases of A2 × T2 and T2 . T2, we anticipate that our technique can be extended to a general method for proving the nonexistence of planar algebras with a specified principal graph.During the preparation of this manuscript, we learnt of Liu's independent result on composites of A3 and A4 subfactor planar algebras (arxiv:1308.5691). In 1994, BischHaagerup showed that the principal graph of a composite of A3 and A4 must fit into a certain family, and Liu has classified all such subfactor planar algebras. We explain the connection between the quotient categories and the corresponding composite subfactor planar algebras. As a corollary of Liu's result, there are no such quotient categories for n ≥ 4.This is an abridged version of arxiv:1308.5723.

APA, Harvard, Vancouver, ISO, and other styles

46

Fayolle, Pierre-Alain, Alexander Pasko, Benjamin Schmitt, and Nikolay Mirenkov. "Constructive Heterogeneous Object Modeling Using Signed Approximate Real Distance Functions." Journal of Computing and Information Science in Engineering 6, no. 3 (November 25, 2005): 221–29. http://dx.doi.org/10.1115/1.2218366.

Full text

Abstract:

We introduce a smooth approximation of the min∕max operations, called signed approximate real distance function (SARDF), for maintaining an approximate signed distance function in constructive shape modeling. We apply constructive distance-based shape modeling to design objects with heterogeneous material distribution in the constructive hypervolume model framework. The introduced distance approximation helps intuitively model material distributions parametrized by distances to so-called material features. The smoothness of the material functions, provided here by the smoothness of the defining function for the shape, helps to avoid undesirable singularities in the material distribution, like stress or concentrations. We illustrate application of the SARDF operations by two- and three-dimensional heterogeneous object modeling case studies.

APA, Harvard, Vancouver, ISO, and other styles

47

BARLET, D., and M. KADDAR. "INCIDENCE DIVISOR." International Journal of Mathematics 14, no. 04 (June 2003): 339–59. http://dx.doi.org/10.1142/s0129167x03001867.

Full text

Abstract:

Let Z be a complex manifold of dimension n+1 and (Xs)s∈S be an analytic family of n-cycles (not necessarily compact) parametrized by a reduced analytic complex space S. Denote by X the graph of this family and p1 (resp. p2) the canonical projection of S × Z on S (resp. on Z). The construction of Barlet-Magnusson assigns to each n+1-codimensionnal subspace in Z which is assumed to be a local complete intersection and to satisfy: C1[Formula: see text] is proper and finite on its image which is nowhere dense in S, an effective Cartier divisor ΣY in S. Nice functorial properties of this correspondance are proven. The purpose of this article is to generalize this result in several directions: using the relative fundamental class of the family (Xs)s∈S in Deligne cohomology, we prove the following results: (1) ΣY depends only on the cycle underlying the locally complete intersection ideal defining Y in Z (2) we generalize the construction of the incidence divisor which is Cartier and effective for any cycle Y (no nilpotent structure on Y is needed) satifying the weaker condition C2[Formula: see text] is proper and generically finite on its image which is nowhere dense in S and we extend the nice functorial properties to this case.

APA, Harvard, Vancouver, ISO, and other styles

48

Giacomini, Matteo, Luca Borchini, Ruben Sevilla, and Antonio Huerta. "Separated response surfaces for flows in parametrised domains: Comparison of a priori and a posteriori PGD algorithms." Finite Elements in Analysis and Design 196 (November 2021): 103530. http://dx.doi.org/10.1016/j.finel.2021.103530.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Badescu, Mircea, and Constantinos Mavroidis. "Workspace Optimization of 3-Legged UPU and UPS Parallel Platforms With Joint Constraints." Journal of Mechanical Design 126, no. 2 (March 1, 2004): 291–300. http://dx.doi.org/10.1115/1.1667922.

Full text

Abstract:

In this paper the workspace optimization of 3-legged translational UPU and orientational UPS parallel platforms under joint constraints is performed. The workspace of both platforms is parametrized using several design parameters that span a large range of values. In this paper both the unconstrained and the constrained workspaces (i.e., workspace with joint limits) are used. For the workspace of each design configuration three performance indices are calculated using a Monte Carlo method: a) the workspace volume; b) the average of the inverse of the condition number and c) a Global Condition Index which is a combination of the other indices. Plots of each performance index as a function of the design parameters are generated and optimal values for these design parameters are determined. For the optimal design, it is shown that by introducing joint limits, the global isotropy of the parallel platforms is improved at the cost of workspace reduction.

APA, Harvard, Vancouver, ISO, and other styles

50

Yang, D. C. H., and Fu-Chung Wang. "A Quintic Spline Interpolator for Motion Command Generation of Computer-Controlled Machines." Journal of Mechanical Design 116, no. 1 (March 1, 1994): 226–31. http://dx.doi.org/10.1115/1.2919351.

Full text

Abstract:

This paper presents a new method of motion command generation for computer controlled multi-axis machines. The method is based on a quintic spline interpolator (QSI) which generates motion commands to trace a set of desired discrete position data via a composite quintic spline (CQS). This CQS is nearly arc length parametrized and has second order continuous at the data points. Consequently, the generated motion trajectories are continuous in both velocity and acceleration throughout the motion. A quick motion command generation scheme is also developed. Compared to the existing linear interpolator (LI), the proposed method takes comparable execution time, but is superior in many other aspects, including position accuracy, speed smoothness, acceleration continuity, torque requirement, and jerk reduction. Compared to the existing cubic spline interpolator (CSI), the proposed method is able to maintain a similarly smooth composite profile, but better speed accuracy. On-line implementation of this interpolator is believed very promising.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Parametrized graphs'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles