Arboricity and bipartite subgraph listing algorithms

DOI10.1016/0020-0190(94)90121-XzbMath0813.68115OpenAlexW2079535727MaRDI QIDQ1334644

David Eppstein

Publication date: 25 September 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90121-x

zbMATH Keywords

bipartite subgraphsbounded arboricity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

On computing the Galois lattice of bipartite distance hereditary graphs, Scale reduction techniques for computing maximum induced bicliques, The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics, Unnamed Item, Computing dense and sparse subgraphs of weakly closed graphs, Compact labelings for efficient first-order model-checking, On linear algebraic algorithms for the subgraph matching problem and its variants, Finding small complete subgraphs efficiently, Ramified rectilinear polygons: coordinatization by dendrons, Unnamed Item, Tight lower bounds on the number of bicliques in false-twin-free graphs, A convexity upper bound for the number of maximal bicliques of a bipartite graph, A Constructive Arboricity Approximation Scheme, Efficient enumeration of maximal induced bicliques, Consensus algorithms for the generation of all maximal bicliques, An approximation ratio for biclustering, Counting Subgraphs in Relational Event Graphs, Faster algorithms for counting subgraphs in sparse graphs, Fully dynamic arboricity maintenance, On the generation of bicliques of a graph, An algebraic semigroup method for discovering maximal frequent itemsets

Cites Work

• Unnamed Item
• Unnamed Item
• Planar orientations with low out-degree and compaction of adjacency matrices
• Pattern associativity and the retrieval of semantic networks
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Can visibility graphs be represented compactly?
• Edge-Disjoint Spanning Trees of Finite Graphs
• Arboricity and Subgraph Listing Algorithms
• Algorithmic Aspects of Vertex Elimination on Graphs
• Connectivity, graph minors, and subgraph multiplicity