Connectedness of graphs and its application to connected matroids through covering-based rough sets
Graph theoretical ideas are highly utilized by computer science fields especially data mining. In this field, a data structure can be designed in the form of tree. Covering is a widely used form of data representation in data mining and covering-based rough sets provide a systematic approach to this type of representation. In this paper, we study the connectedness of graphs through covering-based rough sets and apply it to connected matroids. First, we present an approach to inducing a covering by a graph, and then study the connectedness of the graph from the viewpoint of the covering approximation operators. Second, we construct a graph from a matroid, and find the matroid and the graph have the same connectedness, which makes us to use covering-based rough sets to study connected matroids. In summary, this paper provides a new approach to studying graph theory and matroid theory.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Connectedness Constraint for Learning Sparse Graphs
Graphs are naturally sparse objects that are used to study many problems involving networks, for example, distributed learning and graph signal processing. In some cases, the graph is not given, but must be learned from …
On the Expressibility of the Reconstructional Color Refinement
One of the most basic facts related to the famous Ulam reconstruction conjecture is that the connectedness of a graph can be determined by the deck of its vertex-deleted subgraphs, which are considered up to isomorphism.…
Connectivity for matroids based on rough sets
In mathematics and computer science, connectivity is one of the basic concepts of matroid theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It …
RelationTotal, asymmetric and frequency connectedness between oil and forex markets
We analyze total, asymmetric and frequency connectedness between oil and forex markets using high-frequency, intra-day data over the period 2007 -- 2017. By employing variance decompositions and their spectral representa…
Matroids Hitting Sets and Unsupervised Dependency Grammar Induction
This paper formulates a novel problem on graphs: find the minimal subset of edges in a fully connected graph, such that the resulting graph contains all spanning trees for a set of specifed sub-graphs. This formulation i…
Dependency Grammar Induction