The Experts below are selected from a list of 31863 Experts worldwide ranked by ideXlab platform
Shu Lin - One of the best experts on this subject based on the ideXlab platform.
-
on short cycle enumeration in biregular Bipartite Graphs
IEEE Transactions on Information Theory, 2018Co-Authors: Ian F Blake, Shu LinAbstract:A number of recent works have used a variety of combinatorial constructions to derive Tanner Graphs for LDPC codes and some of these LDPC codes have been shown to perform well in terms of their probability of errors and error floors. Such Graphs are Bipartite and many of these constructions yield biregular Graphs, where the degree of left vertices is a constant $c+1$ and that of the right vertices is a constant $d+1$ . Such Graphs are termed $(c+1,d+1)$ biregular Bipartite Graphs. Two properties of interest in such work is the girth of the graph and the number of short cycles in the graph, cycles of length either the girth or slightly larger. Such numbers have been shown to be related to the error floor of the probability of error curve of the related LDPC code. Using known results of graph theory, it is shown how the girth and the number of cycles of length equal to the girth may be computed for these $(c+1, d+1)$ biregular Bipartite Graphs knowing only the parameters $c$ and $d$ and the numbers of left and right vertices. While numerous algorithms to determine the number of short cycles in arbitrary Graphs exist, the reduction of the problem from an algorithm to a computation for these biregular Bipartite Graphs is of interest.
-
on short cycle enumeration in biregular Bipartite Graphs
arXiv: Information Theory, 2017Co-Authors: Ian F Blake, Shu LinAbstract:A number of recent works have used a variety of combinatorial constructions to derive Tanner Graphs for LDPC codes and some of these have been shown to perform well in terms of their probability of error curves and error floors. Such Graphs are Bipartite and many of these constructions yield biregular Graphs where the degree of left vertices is a constant $c+1$ and that of the right vertices is a constant $d+1$. Such Graphs are termed $(c+1,d+1)$ biregular Bipartite Graphs here. One property of interest in such work is the girth of the graph and the number of short cycles in the graph, cycles of length either the girth or slightly larger. Such numbers have been shown to be related to the error floor of the probability of error curve of the related LDPC code. Using known results of graph theory, it is shown how the girth and the number of cycles of length equal to the girth may be computed for these $(c+1,d+1)$ biregular Bipartite Graphs knowing only the parameters $c$ and $d$ and the numbers of left and right vertices. While numerous algorithms to determine the number of short cycles in arbitrary Graphs exist, the reduction of the problem from an algorithm to a computation for these biregular Bipartite Graphs is of interest.
Ian F Blake - One of the best experts on this subject based on the ideXlab platform.
-
on short cycle enumeration in biregular Bipartite Graphs
IEEE Transactions on Information Theory, 2018Co-Authors: Ian F Blake, Shu LinAbstract:A number of recent works have used a variety of combinatorial constructions to derive Tanner Graphs for LDPC codes and some of these LDPC codes have been shown to perform well in terms of their probability of errors and error floors. Such Graphs are Bipartite and many of these constructions yield biregular Graphs, where the degree of left vertices is a constant $c+1$ and that of the right vertices is a constant $d+1$ . Such Graphs are termed $(c+1,d+1)$ biregular Bipartite Graphs. Two properties of interest in such work is the girth of the graph and the number of short cycles in the graph, cycles of length either the girth or slightly larger. Such numbers have been shown to be related to the error floor of the probability of error curve of the related LDPC code. Using known results of graph theory, it is shown how the girth and the number of cycles of length equal to the girth may be computed for these $(c+1, d+1)$ biregular Bipartite Graphs knowing only the parameters $c$ and $d$ and the numbers of left and right vertices. While numerous algorithms to determine the number of short cycles in arbitrary Graphs exist, the reduction of the problem from an algorithm to a computation for these biregular Bipartite Graphs is of interest.
-
on short cycle enumeration in biregular Bipartite Graphs
arXiv: Information Theory, 2017Co-Authors: Ian F Blake, Shu LinAbstract:A number of recent works have used a variety of combinatorial constructions to derive Tanner Graphs for LDPC codes and some of these have been shown to perform well in terms of their probability of error curves and error floors. Such Graphs are Bipartite and many of these constructions yield biregular Graphs where the degree of left vertices is a constant $c+1$ and that of the right vertices is a constant $d+1$. Such Graphs are termed $(c+1,d+1)$ biregular Bipartite Graphs here. One property of interest in such work is the girth of the graph and the number of short cycles in the graph, cycles of length either the girth or slightly larger. Such numbers have been shown to be related to the error floor of the probability of error curve of the related LDPC code. Using known results of graph theory, it is shown how the girth and the number of cycles of length equal to the girth may be computed for these $(c+1,d+1)$ biregular Bipartite Graphs knowing only the parameters $c$ and $d$ and the numbers of left and right vertices. While numerous algorithms to determine the number of short cycles in arbitrary Graphs exist, the reduction of the problem from an algorithm to a computation for these biregular Bipartite Graphs is of interest.
R Sritharan - One of the best experts on this subject based on the ideXlab platform.
-
strongly chordal and chordal Bipartite Graphs are sandwich monotone
Journal of Combinatorial Optimization, 2011Co-Authors: Pinar Heggernes, Federico Mancini, Charis Papadopoulos, R SritharanAbstract:A graph class is sandwich monotone if, for every pair of its Graphs G 1=(V,E 1) and G 2=(V,E 2) with E 1?E 2, there is an ordering e 1,?,e k of the edges in E 2?E 1 such that G=(V,E 1?{e 1,?,e i }) belongs to the class for every i between 1 and k. In this paper we show that strongly chordal Graphs and chordal Bipartite Graphs are sandwich monotone, answering an open question by Bakonyi and Bono (Czechoslov. Math. J. 46:577---583, 1997). So far, very few classes have been proved to be sandwich monotone, and the most famous of these are chordal Graphs. Sandwich monotonicity of a graph class implies that minimal completions of arbitrary Graphs into that class can be recognized and computed in polynomial time. For minimal completions into strongly chordal or chordal Bipartite Graphs no polynomial-time algorithm has been known. With our results such algorithms follow for both classes. In addition, from our results it follows that all strongly chordal Graphs and all chordal Bipartite Graphs with edge constraints can be listed efficiently.
-
strongly chordal and chordal Bipartite Graphs are sandwich monotone
Computing and Combinatorics Conference, 2009Co-Authors: Pinar Heggernes, Federico Mancini, Charis Papadopoulos, R SritharanAbstract:A graph class is sandwich monotone if, for every pair of its Graphs G 1 = (V ,E 1 ) and G 2 = (V ,E 2 ) with E 1 *** E 2 , there is an ordering e 1 , ..., e k of the edges in E 2 *** E 1 such that G = (V , E 1 *** {e 1 , ..., e i }) belongs to the class for every i between 1 and k . In this paper we show that strongly chordal Graphs and chordal Bipartite Graphs are sandwich monotone, answering an open question by Bakonyi and Bono from 1997. So far, very few classes have been proved to be sandwich monotone, and the most famous of these are chordal Graphs. Sandwich monotonicity of a graph class implies that minimal completions of arbitrary Graphs into that class can be recognized and computed in polynomial time. For minimal completions into strongly chordal or chordal Bipartite Graphs no polynomial-time algorithm has been known. With our results such algorithms follow for both classes. In addition, from our results it follows that all strongly chordal Graphs and all chordal Bipartite Graphs with edge constraints can be listed efficiently.
-
the induced matching and chain subgraph cover problems for convex Bipartite Graphs
Theoretical Computer Science, 2007Co-Authors: Andreas Brandstadt, Elaine M Eschen, R SritharanAbstract:We present an O(n^2)-time algorithm for computing a maximum cardinality induced matching and a minimum cardinality cover by chain subGraphs for convex Bipartite Graphs. This improves the previous time bound of O(m^2).
J Sheehan - One of the best experts on this subject based on the ideXlab platform.
-
irreducible pseudo 2 factor isomorphic cubic Bipartite Graphs
Designs Codes and Cryptography, 2012Co-Authors: Marien Abreu, D Labbate, J SheehanAbstract:A Bipartite graph is pseudo 2-factor isomorphic if the number of circuits in each 2-factor of the graph is always even or always odd. We proved (Abreu et al., J Comb Theory B 98:432---442, 2008) that the only essentially 4-edge-connected pseudo 2-factor isomorphic cubic Bipartite graph of girth 4 is K 3,3, and conjectured (Abreu et al., 2008, Conjecture 3.6) that the only essentially 4-edge-connected cubic Bipartite Graphs are K 3,3, the Heawood graph and the Pappus graph. There exists a characterization of symmetric configurations n 3 due to Martinetti (1886) in which all symmetric configurations n 3 can be obtained from an infinite set of so called irreducible configurations (Martinetti, Annali di Matematica Pura ed Applicata II 15:1---26, 1888). The list of irreducible configurations has been completed by Boben (Discret Math 307:331---344, 2007) in terms of their irreducible Levi Graphs. In this paper we characterize irreducible pseudo 2-factor isomorphic cubic Bipartite Graphs proving that the only pseudo 2-factor isomorphic irreducible Levi Graphs are the Heawood and Pappus Graphs. Moreover, the obtained characterization allows us to partially prove the above Conjecture.
-
irreducible pseudo 2 factor isomorphic cubic Bipartite Graphs
arXiv: Combinatorics, 2010Co-Authors: Marien Abreu, D Labbate, J SheehanAbstract:A Bipartite graph is {\em pseudo 2--factor isomorphic} if all its 2--factors have the same parity of number of circuits. In \cite{ADJLS} we proved that the only essentially 4--edge-connected pseudo 2--factor isomorphic cubic Bipartite graph of girth 4 is $K_{3,3}$, and conjectured \cite[Conjecture 3.6]{ADJLS} that the only essentially 4--edge-connected cubic Bipartite Graphs are $K_{3,3}$, the Heawood graph and the Pappus graph. There exists a characterization of symmetric configurations $n_3$ %{\bf decide notation and how to use it in the rest of the paper} due to Martinetti (1886) in which all symmetric configurations $n_3$ can be obtained from an infinite set of so called {\em irreducible} configurations \cite{VM}. The list of irreducible configurations has been completed by Boben \cite{B} in terms of their {\em irreducible Levi Graphs}. In this paper we characterize irreducible pseudo 2--factor isomorphic cubic Bipartite Graphs proving that the only pseudo 2--factor isomorphic irreducible Levi Graphs are the Heawood and Pappus Graphs. Moreover, the obtained characterization allows us to partially prove the above Conjecture.
Zhang Y - One of the best experts on this subject based on the ideXlab platform.
-
Hurricane in Bipartite Graphs: The Lethal Nodes of Butterflies
'Association for Computing Machinery (ACM)', 2021Co-Authors: Zhu Q, Zheng J, Yang H, Chen C, Wang X, Zhang YAbstract:Bipartite Graphs are widely used when modeling the relationships between two different types of entities, such as purchase relationships. In a Bipartite graph, the number of butterflies, i.e., 2 × 2 biclique, is a fundamental metric for analyzing the structures and properties of Bipartite Graphs. Considering the deletion of critical nodes may affect the stability of Bipartite Graphs, we propose the butterfly minimization problem, where the attacker aims to maximize the number of butterflies removed from the graph by deleting b nodes. We prove the problem is NP-hard, and the objective function is monotonic and submodular. We adopt a greedy algorithm to solve the problem with 1-1/e approximation ratio. To scale for large Graphs, novel methods are developed to reduce the searching space. Experiments over real-world Bipartite Graphs are conducted to demonstrate the advantages of proposed techniques
-
Efficiently answering reachability and path queries on temporal Bipartite Graphs
'VLDB Endowment', 2021Co-Authors: Chen X, Wang K, Lin X, Zhang W, Qin L, Zhang YAbstract:Bipartite Graphs are naturally used to model relationships between two different types of entities, such as people-location, authorpaper, and customer-product. When modeling real-world applications like disease outbreaks, edges are often enriched with temporal information, leading to temporal Bipartite Graphs. While reachability has been extensively studied on (temporal) unipartite Graphs, it remains largely unexplored on temporal Bipartite Graphs. To fill this research gap, in this paper, we study the reachability problem on temporal Bipartite Graphs. Specifically, a vertex u reaches a vertex w in a temporal Bipartite graph G if u and w are connected through a series of consecutive wedges with time constraints. Towards efficiently answering if a vertex can reach the other vertex, we propose an index-based method by adapting the idea of 2-hop labeling. Effective optimization strategies and parallelization techniques are devised to accelerate the index construction process. To better support real-life scenarios, we further show how the index is leveraged to efficiently answer other types of queries, e.g., singlesource reachability query and earliest-arrival path query. Extensive experiments on 16 real-world Graphs demonstrate the effectiveness and efficiency of our proposed techniques
-
Towards efficient solutions of bitruss decomposition for large-scale Bipartite Graphs
'Springer Science and Business Media LLC', 2021Co-Authors: Wang K, Lin X, Zhang W, Qin L, Zhang YAbstract:In recent years, cohesive subgraph mining in Bipartite Graphs becomes a popular research topic. An important cohesive subgraph model k-bitruss is the maximal cohesive subgraph where each edge is contained in at least k butterflies (i.e., (2, 2)-bicliques). In this paper, we study the bitruss decomposition problem which aims to find all the k-bitrusses for k≥ 0. The existing algorithms follow a bottom-up strategy which peels the edges with the lowest butterfly support iteratively. In this peeling process, these algorithms are time-consuming to enumerate all the supporting butterflies for each edge. To solve this issue, we propose a novel online index, the BE-Index which compresses butterflies into k-blooms (i.e., (2, k)-bicliques). Based on the BE-Index, the new bitruss decomposition algorithm BiT-BU is proposed, along with two batch-based optimizations, to accomplish the butterfly enumeration of the peeling process efficiently. Furthermore, the BiT-PC algorithm is designed which is more efficient against handling the edges with high butterfly supports. Besides, we explore shared-memory parallel solutions to handle large Graphs in a more efficient way. In the parallel algorithms, we propose effective techniques to reduce conflicts among threads. We theoretically show that our new algorithms significantly reduce the time complexities of the existing algorithms. In addition, extensive empirical evaluations are conducted on real-world datasets. The experimental results further validate the effectiveness of the bitruss model and demonstrate that our proposed solutions significantly outperform the state-of-the-art techniques by several orders of magnitude
-
Exploring cohesive subGraphs with vertex engagement and tie strength in Bipartite Graphs
'Elsevier BV', 2021Co-Authors: He Y, Lin X, Wang K, Zhang W, Zhang YAbstract:We propose a novel cohesive subgraph model called τ-strengthened (α,β)-core (denoted as (α,β)τ-core), which is the first to consider both tie strength and vertex engagement on Bipartite Graphs. An edge is a strong tie if contained in at least τ butterflies (2×2-bicliques). (α,β)τ-core requires each vertex on the upper or lower level to have at least α or β strong ties, given strength level τ. To retrieve the vertices of (α,β)τ-core optimally, we construct index Iα,β,τ to store all (α,β)τ-cores. Effective optimization techniques are proposed to improve index construction. To make our idea practical on large Graphs, we propose 2D-indexes Iα,β,Iβ,τ, and Iα,τ that selectively store the vertices of (α,β)τ-core for some α,β, and τ. The 2D-indexes are more space-efficient and require less construction time, each of which can support (α,β)τ-core queries. As query efficiency depends on input parameters and the choice of 2D-index, we propose a learning-based hybrid computation paradigm by training a feed-forward neural network to predict the optimal choice of 2D-index that minimizes the query time. Extensive experiments show that (1) (α,β)τ-core is an effective model capturing unique and important cohesive subGraphs; (2) the proposed techniques significantly improve the efficiency of index construction and query processing
