期刊文献+
任意字段
题名或关键词
题名
关键词
摘要
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到195篇文章
< 1 2 … 10 >
每页显示 20 50 100
已选0条
引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
Maximization of monotone non-k-submodular set function with noise under matroid constraints 认领 引用
1
作者 Jiang Yanjun Wang Yijing +1 位作者 Yang Ruiqi Li Ali 《High Technology Letters》 EI CAS 2026年第1期73-83,共11页
Submodular optimization is primarily applied in multi-agent systems for tasks such as resource allocation,task assignment,collaborative decision-making,and optimization problems.Maximization of optimizing submodular s... Submodular optimization is primarily applied in multi-agent systems for tasks such as resource allocation,task assignment,collaborative decision-making,and optimization problems.Maximization of optimizing submodular set functions attracts much attention since the 1970s.A large body of work has been done using approximation algorithms.When the dimension of the independent variable of the set function changes from one tok,it is called ak-submodular set function.Thek-submodular set function,a generalization of the classical submodular set function,arises in diverse fields with varied applications.In many practical scenarios,quantifying the degree of closeness to submodularity becomes essential,leading to concepts such as approximately submodular set functions and the diminishing-return(DR) ratio.This paper investigates ak-dimensional set function under matroid constraints,which may lack full submodularity.Instead,we focus on an approximately non-ksubmodular set function characterized by its DR ratio.Employing a greedy algorithmic approach,we derive an approximation guarantee for this problem.Notably,when the DR ratio is set to one,our results align with existing findings in the literature.Experimental results demonstrate the superiority of our algorithm over the baselines. 展开更多
关键词 k-submodular set function greedy matroid constraints approximation algorithm
暂未订购 下载PDF
Min-max partitioning problem with matroid constraint 认领 引用
2
作者 Biao WU En-yu YAO 《Journal of Zhejiang University-SCIENCE A》 SCIE EI CAS 2008年第10期1446-1450,共5页
In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an appro... In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an approximation algorithm, which consists of two sub-algorithms-the modified Edmonds' matroid partitioning algorithm and the exchange algorithm, for the problem. An estimation of the worst ratio for the algorithm is given. 展开更多
关键词 Matroid Matroid partition Worst ratio
暂未订购 下载PDF
Two Results on Binary Matroids 认领 引用
3
作者 孙良 赵军 杨刚 《Journal of Beijing Institute of Technology》 EI CAS 1998年第1期1-5,共5页
Aim To research new characterization and circuit property of binary matroid. Methods Constract the modular pairs of hyperplanes of a a matroid. Results and Conclusion It is proved that a matroid M on finite set S is b... Aim To research new characterization and circuit property of binary matroid. Methods Constract the modular pairs of hyperplanes of a a matroid. Results and Conclusion It is proved that a matroid M on finite set S is binary if and only if for any two distinct hyper-planes H1 and H2, if H1H2S ,and H1 and H2 are modular pair, then S-(H1H2) is a hyperplande .And a necessary and sufficient condition for a binary matroid to have a k-circuit is obtained. 展开更多
关键词 matroid hyperplane circuit cocircuit
暂未订购 下载PDF
Extreme Matroid Graphs 认领 引用
4
作者 王世英 殷志祥 《Northeastern Mathematical Journal》 2003年第1期19-25,共7页
Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.
关键词 extreme matroid graph extreme set bicritical graph
暂未订购 下载PDF
The Facets of the Bases Polytope of a Matroid and Two Consequences 认领 引用
5
作者 Brahim Chaourar 《Open Journal of Discrete Mathematics》 2018年第1期14-20,共7页
Let M be a matroid defined on a finite set E and L?&#8834;?E?. L is locked in M if??and ?are 2-connected, and . In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the lo... Let M be a matroid defined on a finite set E and L?&#8834;?E?. L is locked in M if??and ?are 2-connected, and . In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the locked subsets. We deduce that finding the maximum-weight basis of M is a polynomial time problem for matroids with a polynomial number of locked subsets. This class of matroids is closed under 2-sums and contains the class of uniform matroids, the Vámos matroid and all the excluded minors of 2-sums of uniform matroids. We deduce also a matroid oracle for testing uniformity of matroids after one call of this oracle. 展开更多
关键词 Bases Polytope Facets Locked Subsets Maximum-Weight Basis Problem Polynomially Locked Matroids Matroid Oracle Testing Unformity of a Matroid
暂未订购 下载PDF
Matroidal Error Correction Networks and Linear Network Error Correction MDS Codes 认领 引用
6
作者 ZHOU Hang LIU Guangjun 《Wuhan University Journal of Natural Sciences》 CAS 2013年第6期477-483,共7页
In this paper, we further study the connections between linear network error correction codes and representable matroids. We extend the concept of matroidal network introduced by Dougherty et al. to a generalized case... In this paper, we further study the connections between linear network error correction codes and representable matroids. We extend the concept of matroidal network introduced by Dougherty et al. to a generalized case when errors occur in multi- ple channels. Importantly, we show the necessary and sufficient conditions on the existence of linear network error correction mul- ticast/broadcast/dispersion maximum distance separable （MDS） code on a matroidal error correction network. 展开更多
关键词 network error correction code error pattern imagi-nary error channels extended network matroid
暂未订购 下载PDF
Vertex Disjoint Cycles in Intersection Graphs of Bases of Matroids 认领 引用
7
作者 ZHANG Yinghao CHI Hongmei 《Wuhan University Journal of Natural Sciences》 CAS CSCD 2017年第6期461-464,共4页
The intersection graph of bases of a matroid M=（E, B） is a graph G=GI（M） with vertex set V（G） and edge set E（G） such that V（G）=B（M） and E（G）={BB′：｜B∩B′｜ ≠0, B, B′∈B（M）, where the same notation... The intersection graph of bases of a matroid M=（E, B） is a graph G=GI（M） with vertex set V（G） and edge set E（G） such that V（G）=B（M） and E（G）={BB′：｜B∩B′｜ ≠0, B, B′∈B（M）, where the same notation is used for the vertices of G and the bases of M. Suppose that｜V（GI（M））｜ =n and k1＋k2＋…＋kp=n, where ki is an integer, i=1, 2,…, p. In this paper, we prove that there is a partition of V（GI（M）） into p parts V1 , V2,…, Vp such that ｜Vi｜ =ki and the subgraph Hi induced by Vi contains a ki-cycle when ki ≥3, Hi is isomorphic to K2 when ki =2 and Hi is a single point when ki =1. 展开更多
关键词 matroid intersection graph base cycle
暂未订购 下载PDF
Relationships among Matroids Induced by Covering-Based Upper Approximation Operators 认领 引用
8
作者 Lirun SU 《Journal of Mathematical Research with Applications》 CSCD 2018年第4期351-365,共15页
Covering-based rough sets,as a technique of granular computing,can be a useful tool for dealing with inexact,uncertain or vague knowledge in information systems.Matroids generalize linear independence in vector spaces... Covering-based rough sets,as a technique of granular computing,can be a useful tool for dealing with inexact,uncertain or vague knowledge in information systems.Matroids generalize linear independence in vector spaces,graph theory and provide well established platforms for greedy algorithm design.In this paper,we construct three types of matroidal structures of covering-based rough sets.Moreover,through these three types of matroids,we study the relationships among these matroids induced by six types of covering-based upper approximation operators.First,we construct three families of sets by indiscernible neighborhoods,neighborhoods and close friends,respectively.Moreover,we prove that they satisfy independent set axioms of matroids.In this way,three types of matroidal structures of covering-based rough sets are constructed.Secondly,we study some characteristics of the three types of matroid,such as dependent sets,circuits,rank function and closure.Finally,by comparing independent sets,we study relationships among these matroids induced by six types of covering-based upper approximation operators. 展开更多
关键词 covering matroid rough set upper approximation operator indiscernible neigh-borhood neighborhood close friend
暂未订购 下载PDF
On Functions of K-Balanced Matroids 认领 引用
9
作者 Talal Al-Hawary 《Open Journal of Discrete Mathematics》 2017年第3期103-107,共5页
In this paper, we prove an analogous to a result of Erd&ouml;s and Rényi and of Kelly and Oxley. We also show that there are several properties of k-balanced matroids for which there exists a threshold function.
关键词 K-Balanced Matroid Projective Geometry Threshold Function
暂未订购 下载PDF
关于MATROID的一个特征性质 认领 引用
10
作者 左可正 《湖北师范学院学报（自然科学版）》 1993年第6期39-41,共3页
本文给出了 Matroid 的一个特征性质,即给出了以下定理:设 S 是集合, 2,Φ∈, 为子集闭的,则（S,）为 Matroid 当且仅当下列条件满足:对X={x1,x2…xn)∈,Y={y1,y2,…ym)∈,X、Y 在 F中极大,则 n=m,且适当调整 xi的顺... 本文给出了 Matroid 的一个特征性质,即给出了以下定理:设 S 是集合, 2,Φ∈, 为子集闭的,则（S,）为 Matroid 当且仅当下列条件满足:对X={x1,x2…xn)∈,Y={y1,y2,…ym)∈,X、Y 在 F中极大,则 n=m,且适当调整 xi的顺序,可使i,{y1…yi-1,xi,yi+1…,ym}∈（i=1,2,…n） 展开更多
关键词 Matroid 秩 闭包 二部图 匹配
暂未订购 下载PDF
Analytic Properties of Speyer’s g-polynomial of Uniform Matroids 认领 引用
11
作者 Rong Zhang James J.Y.Zhao 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2026年第4期1087-1098,共12页
Let Un,ddenote the uniform matroid of rank d on n elements.We obtain some recurrence relations satisfied by Speyer’s g-polynomials gun,d(t)of Un,d.Based on these recurrence relations,we prove that the polyno... Let Un,ddenote the uniform matroid of rank d on n elements.We obtain some recurrence relations satisfied by Speyer’s g-polynomials gun,d(t)of Un,d.Based on these recurrence relations,we prove that the polynomial gun,d(t)has only real zeros for any n-1≥d≥1.Furthermore,we show that the coefficient of gun,[n/2](t)is asymptotically normal by local and central limit theorems. 展开更多
关键词 Speyer’s g-polynomial uniform matroid real zeros interlacing property asymptotic normality
暂未订购 下载PDF
The Connectivity and Minimum Degree of Circuit Graphs of Matroids 认领 引用 被引量：5
12
作者 Ping LI Gui Zhen LIU 《Acta Mathematica Sinica,English Series》 SCIE 2010年第2期353-360,共8页
Let G be the circuit graph of any connected matroid M with minimum degree 5（G）. It is proved that its connectivity κ（G） ≥2｜E（M） - B（M）｜ - 2. Therefore 5（G） ≥ 2｜E（M） - B（M）｜ - 2 and this bound is t... Let G be the circuit graph of any connected matroid M with minimum degree 5（G）. It is proved that its connectivity κ（G） ≥2｜E（M） - B（M）｜ - 2. Therefore 5（G） ≥ 2｜E（M） - B（M）｜ - 2 and this bound is the best possible in some sense. 展开更多
关键词 matroid circuit graph of matroid connectivity
暂未订购 下载PDF
Eulerian and Bipartite Binary Delta-matroids 认领 引用
13
作者 Qi YAN Xian-an JIN 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2022年第4期813-821,共9页
Delta-matroid theory is often thought of as a generalization of topological graph theory.It is well-known that an orientable embedded graph is bipartite if and only if its Petrie dual is orientable.In this paper,we fi... Delta-matroid theory is often thought of as a generalization of topological graph theory.It is well-known that an orientable embedded graph is bipartite if and only if its Petrie dual is orientable.In this paper,we first introduce the concepts of Eulerian and bipartite delta-matroids and then extend the result from embedded graphs to arbitrary binary delta-matroids.The dual of any bipartite embedded graph is Eulerian.We also extend the result from embedded graphs to the class of delta-matroids that arise as twists of binary matroids.Several related results are also obtained. 展开更多
关键词 matroid delta-matroid binary bipartite Eulerian
暂未订购 下载PDF
Properties of Hamilton cycles of circuit graphs of matroids 认领 引用 被引量：5
14
作者 Hao FAN Guizhen LIU 《Frontiers of Mathematics in China》 SCIE CSCD 2013年第4期801-809,共9页
Let G be a circuit graph of a connected matroid.P.Li and G.Liu[Comput.Math.Appl.,2008,55:654-659]proved that G has a Hamilton cycle including e and another Hamilton cycle excluding e for any edge e of G if G has at le... Let G be a circuit graph of a connected matroid.P.Li and G.Liu[Comput.Math.Appl.,2008,55:654-659]proved that G has a Hamilton cycle including e and another Hamilton cycle excluding e for any edge e of G if G has at least four vertices.This paper proves that G has a Hamilton cycle including e and excluding e'for any two edges e and e'of G if G has at least five vertices.This result is best possible in some sense.An open problem is proposed in the end of this paper. 展开更多
关键词 Matroid circuit graph of matroid Hamilton cycle
暂未订购 下载PDF
Global Rank Axioms for Poset Matroids 认领 引用 被引量：5
15
作者 ShuChaoLI YanQinFENG 《Acta Mathematica Sinica,English Series》 SCIE 2004年第3期507-514,共8页
An excellent introduction to the topic of poset matroids is due to Barnabei, Nicoletti and Pezzoli. In this paper, we investigate the rank axioms for poset matroids; thereby we can characterize poset matroids in a “g... An excellent introduction to the topic of poset matroids is due to Barnabei, Nicoletti and Pezzoli. In this paper, we investigate the rank axioms for poset matroids; thereby we can characterize poset matroids in a “global” version and a “pseudo-global” version. Some corresponding properties of combinatorial schemes are also obtained. 展开更多
关键词 Poset matroids Rank function Combinatorial scheme Distributive lattice
暂未订购 下载PDF
k-Submodular Maximization with a Knapsack Constraint and p Matroid Constraints 认领 引用 被引量：2
16
作者 Qian Liu Kemin Yu +1 位作者 Min Li Yang Zhou 《Tsinghua Science and Technology》 SCIE EI CAS CSCD 2023年第5期896-905,共10页
A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets.The k-submodular maximization proble... A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets.The k-submodular maximization problem has a wide range of applications.In this paper,we propose a nested greedy and local search algorithm for the problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints. 展开更多
关键词 k-submodularity knapsack constraint matroid constraint approximation algorithm
暂未订购 下载PDF
New Results on Global Rank Axioms of Poset Matroids 认领 引用 被引量：1
17
作者 ShuChaoLI YanQinFENG 《Acta Mathematica Sinica,English Series》 SCIE 2005年第1期143-154,共12页
An excellent introduction to the topic of poset matroids is due to M.Barnabei, G. Nicoletti and L. Pezzoli. On the basis of their work, we have obtained the global rankaxioms for poset matroids. In this paper, we stud... An excellent introduction to the topic of poset matroids is due to M.Barnabei, G. Nicoletti and L. Pezzoli. On the basis of their work, we have obtained the global rankaxioms for poset matroids. In this paper, we study the special integral function f and obtain a newclass of poset matroids from the old ones, and then we generalize this result according to theproperties of f. Almost all of these results can be regarded as the application of global rankaxioms for poset matroids. The main results in our paper have, indeed, investigated the restrictionof the basis of the poset matroid, and we give them the corresponding geometric interpretation. 展开更多
关键词 Poset matroids Rank function Derivative function Combinatorial schemes
暂未订购 下载PDF
Approximation Algorithms for Maximization of k-Submodular Function Under a Matroid Constraint 认领 引用
18
作者 Yuezhu Liu Yunjing Sun Min Li 《Tsinghua Science and Technology》 SCIE EI CAS CSCD 2024年第6期1633-1641,共9页
In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid constraint.In order to reduce the complexity of this algorithm,we al... In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid constraint.In order to reduce the complexity of this algorithm,we also present a randomized 1/3-approximation algorithm with the probability of 1−ε,whereεis the probability of algorithm failure.Moreover,we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions. 展开更多
关键词 k-submodular matroid constraint deterministic algorithm randomized algorithm streaming algorithm
暂未订购 下载PDF
APPLICATIONS OF MATROID PARTITION TO TREE DECOMPOSITION 认领 引用
19
作者 蔡茂诚 袁旭东 《Acta Mathematicae Applicatae Sinica》 2000年第2期199-204,共6页
In this paper we present a matroid approach to the tree decomposition problem, give alternative proofs of the main results in [1,2], which give the necessary and sufficient conditions for a graph C=(V,E) of order n to... In this paper we present a matroid approach to the tree decomposition problem, give alternative proofs of the main results in [1,2], which give the necessary and sufficient conditions for a graph C=(V,E) of order n to have a tree decomposition (T_1,T_2): (i) Ti is of order n-1 and excludes the specified vertex ui V, i=1,2; (n) TI is a spanning tree, T_2 is of order n-2 and excludes the specified vertices u_l,u_2∈V. As an application, we give a necessary and sufficient condition for a connected graph to have a tree-decomposition of {n-1,n-1}. 展开更多
关键词 Thee graph matroid partition decomposition
暂未订购 下载PDF
PROOF OF A CONJECTURE ON MATROID BASE GRAPHS 认领 引用
20
作者 刘桂真 《Science China Mathematics》 1990年第11期1329-1337,共9页
Let G be the base graph of a matroid. L et k(G),λ(G) and δ(G)denote the connectivity edge-connectivity and the minimum degree of G, respectively. The conjecture that k(G)= λ(G)=δ(G) is proved true for any matroid.
关键词 matroid base graph connectivity.
暂未订购 下载PDF
已选0条
引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 2 … 10 下一页 到第 页
在线咨询 使用帮助 返回顶部 意见反馈