共查询到20条相似文献,搜索用时 15 毫秒
1.
《Discrete Mathematics》2022,345(11):113055
Using the standard Coxeter presentation for the signed symmetric group on letters, two reduced expressions for a given signed permutation are in the same commutation class if one expression can be obtained from the other one by applying a finite sequence of commutations. The commutative classes of a given signed permutation can be seen as the vertices of a graph, called the commutation graph, where two classes are connected by an edge if there are elements in those classes that differ by a long braid relation. We define a rank function for the commutation graph for the longest signed permutation, and use this function to compute the diameter and the radius of the graph. We also prove that the commutation graph for the longest signed permutation is not planar for , and identify the classes with a single element. 相似文献
2.
Pranay Chaudhuri 《BIT Numerical Mathematics》1988,28(1):1-18
This paper presents fast parallel algorithms for the following graph theoretic problems: breadth-depth search of directed acyclic graphs; minimum-depth search of graphs; finding the minimum-weighted paths between all node-pairs of a weighted graph and the critical activities of an activity-on-edge network. The first algorithm hasO(logdlogn) time complexity withO(n
3) processors and the remaining algorithms achieveO(logd loglogn) time bound withO(n
2[n/loglogn]) processors, whered is the diameter of the graph or the directed acyclic graph (which also represents an activity-on-edge network) withn nodes. These algorithms work on an unbounded shared memory model of the single instruction stream, multiple data stream computer that allows both read and write conflicts. 相似文献
3.
We establish a correspondence among loops, regular permutation sets and directed graphs with a suitable edge colouring and relate some algebraic properties of the loop to configurations of the associated graph. 相似文献
4.
Tatjana Nahtman 《Linear algebra and its applications》2006,417(1):183-210
The goal of the present paper is to perform a comprehensive study of the covariance structures in balanced linear models containing random factors which are invariant with respect to marginal permutations of the random factors. We shall focus on model formulation and interpretation rather than the estimation of parameters. It is proven that permutation invariance implies a specific structure for the covariance matrices. Useful results are obtained for the spectra of permutation invariant covariance matrices. In particular, the reparameterization of random effects, i.e., imposing certain constraints, will be considered. There are many possibilities to choose reparameterization constraints in a linear model, however not every reparameterization keeps permutation invariance. The question is if there are natural restrictions on the random effects in a given model, i.e., such reparameterizations which are defined by the covariance structure of the corresponding factor. Examining relationships between the reparameterization conditions applied to the random factors of the models and the spectrum of the corresponding covariance matrices when permutation invariance is assumed, restrictions on the spectrum of the covariance matrix are obtained which lead to “sum-to-zero” reparameterization of the corresponding factor. 相似文献
5.
《Discrete Applied Mathematics》1988,21(3):177-183
We give a linear time reduction of the problem of finding a minimum independent dominating set in a permutation graph, into that of finding a shortest maximal increasing subsequence. We then give an O(n log2n)-time algorithm for solving the second (and hence the first) problem. This improves on the O(n3)-time algorithm given in [4] for solving the problem of finding a minimum independent dominating set in a permutation graph. 相似文献
6.
Lszl Babai 《Journal of Graph Theory》1977,1(2):125-130
Results in diverse areas, such as the Nielsen-Schreier theorem on subgroups of free groups and a proof of A. T. White's conjecture on the genus of subgroups are shown to be immediate consequences of a lemma which has already proved useful in investigating topological properties and automorphism group of graphs. 相似文献
7.
Madhumangal Pal 《Journal of Applied Mathematics and Computing》1998,5(1):141-152
Based on the geometric representation, an efficient algorithm is designed to find all articulation points of a permutation graph. The proposed algorithm takes onlyO(n logn) time andO(n) space, wheren represents the number of vertices. The proposed sequential algorithm can easily be implemented in parallel which takesO(logn) time andO(n) processors on an EREW PRAM. These are the first known algorithms for the problem on this class of graph. 相似文献
8.
9.
Jesper Makholm Byskov 《Operations Research Letters》2004,32(6):547-556
We give tight upper bounds on the number of maximal independent sets of size k (and at least k and at most k) in graphs with n vertices. As an application of the proof, we construct improved algorithms for graph colouring and computing the chromatic number of a graph. 相似文献
11.
Richard A. Brualdi 《Linear and Multilinear Algebra》1979,7(1):1-12
Dedicated to Leon Mirsky on the occasion of his sixtieth birthday. 相似文献
12.
Noga Alon 《Journal of Combinatorial Theory, Series A》1985,40(1):82-89
Let X1, …, Xn be n disjoint sets. For 1 ? i ? n and 1 ? j ? h let Aij and Bij be subsets of Xi that satisfy |Aij| ? ri and |Bij| ? si for 1 ? i ? n, 1 ? j ? h, for 1 ? j ? h, for 1 ? j < l ? h. We prove that . This result is best possible and has some interesting consequences. Its proof uses multilinear techniques (exterior algebra). 相似文献
13.
Milovanovi Emina Bozkurt Altinda erife Burcu Mateji Marjan Milovanovi Igor 《Czechoslovak Mathematical Journal》2022,72(3):783-799
Czechoslovak Mathematical Journal - Let a = (a1,a2, …, an) be a nonincreasing sequence of positive real numbers. Denote by S = {1, 2, …, n} the index set and by Jk = {I = {r1, r2,... 相似文献
14.
《European Journal of Operational Research》2005,164(3):680-689
Many problems found in standard security and survivability applications can be transformed into graph and scheduling problems, thereby opening up the problems to a wealth of potential solutions or knowledge of limitations, infeasibility, scalability or intractability. This paper introduces a model to aid in the design, analysis, or operations of applications with security and survivability concerns. Specifically, a five step model is presented that transforms such applications into a parameterized graph model that, together with model abstraction and representations, can be the basis for solutions derived from graph and scheduling algorithms. A reverse transformation translates the solutions back to the application domain. The model is demonstrated using migratory agent security and fault-tolerant agreement and their transformation into chain constrained and group scheduling problems, respectively. 相似文献
15.
16.
Continuing our previous work(ar Xiv:1509.07981v1),we derive another global gradient estimate for positive functions,particularly for positive solutions to the heat equation on finite or locally finite graphs.In general,the gradient estimate in the present paper is independent of our previous one.As applications,it can be used to get an upper bound and a lower bound of the heat kernel on locally finite graphs.These global gradient estimates can be compared with the Li–Yau inequality on graphs contributed by Bauer et al.[J.Differential Geom.,99,359–409(2015)].In many topics,such as eigenvalue estimate and heat kernel estimate(not including the Liouville type theorems),replacing the Li–Yau inequality by the global gradient estimate,we can get similar results. 相似文献
17.
In a series of papers, of which the present one is Part I, it is shown that solutions to a variety of problems in distance geometry, potential theory and theory of metric spaces are provided by appropriate applications of graph theoretic results. 相似文献
18.
《Discrete Mathematics》2006,306(10-11):853-866
In a series of papers, of which the present one is Part I, it is shown that solutions to a variety of problems in distance geometry, potential theory and theory of metric spaces are provided by appropriate applications of graph theoretic results. 相似文献
19.
Jiang Jiahe 《数学学报(英文版)》1997,13(3):389-406
In the present paper there are given a number of minimax-type inequalities for a family of functions, involving two multivalued
mappings, one being strongly decomposable and the other monotone. Hence some applications to the variational-type inequality
theory and to the fixed point theory.
Supported both by the National Natural Science Foundation of China and by the Institute of Mathematics, Academia Sinica 相似文献
20.
Armengol Gasull Chengzhi Li Joan Torregrosa 《Journal of Differential Equations》2012,252(2):1635-1641
We prove that a family of functions defined through some definite integrals forms an extended complete Chebyshev system. The key point of our proof consists of reducing the study of certain Wronskians to the Gram determinants of a suitable set of new functions. Our result is then applied to give upper bounds for the number of isolated periodic solutions of some perturbed Abel equations. 相似文献