Arboricity and Subgraph Listing Algorithms
From MaRDI portal
Publication:3690237
DOI10.1137/0214017zbMath0572.68053OpenAlexW2055245094WikidataQ55891719 ScholiaQ55891719MaRDI QIDQ3690237
Norishige Chiba, Takao Nishizeki
Publication date: 1985
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/0d19245a27bc65a87a8014d5b8a66fb514c8ff0b
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Related Items
A new algorithm for embedding plane graphs at fixed vertex locations, Arboricity and bipartite subgraph listing algorithms, Counting Subgraphs in Degenerate Graphs, SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES, Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem, Finding and counting small induced subgraphs efficiently, Dynamic Set Intersection, Simultaneously load balancing for every p-norm, with reassignments, Fast Quasi-Threshold Editing, Map graphs having witnesses of large girth, Computing median and antimedian sets in median graphs, Sublinear-time distributed algorithms for detecting small cliques and even cycles, The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics, Approximating the minimum triangulation of convex 3-polytopes with bounded degrees, Efficiently enumerating all maximal cliques with bit-parallelism, The worst-case time complexity for generating all maximal cliques and computational experiments, Fast recognition of classes of almost-median graphs, Recognizing IC-Planar and NIC-Planar Graphs, New applications of clique separator decomposition for the maximum weight stable set problem, Triangulated neighborhoods in even-hole-free graphs, On the thickness and arboricity of a graph, iTri: index-based triangle listing in massive graphs, Homothetic polygons and beyond: maximal cliques in intersection graphs, \(\mathsf{NIC}\)-planar graphs, Mind the gap!, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems, Counting Homomorphic Cycles in Degenerate Graphs, Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs, On the general Randić index of polymeric networks modelled by generalized Sierpiński graphs, Approximately Counting Triangles in Sublinear Time, Computing dense and sparse subgraphs of weakly closed graphs, The challenges of unbounded treewidth in parameterised subgraph counting problems, Summarized bit batch-based triangle listing in massive graphs, A more compact visibility representation, Arboricity, \(h\)-index, and dynamic algorithms, On linear algebraic algorithms for the subgraph matching problem and its variants, Random Walks on Simplicial Complexes and the Normalized Hodge 1-Laplacian, Finding small complete subgraphs efficiently, Dominoes, Finding large planar subgraphs and large subgraphs of a given genus, On the generalized Helly property of hypergraphs, cliques, and bicliques, Arc diagrams, flip distances, and Hamiltonian triangulations, On Approximating the Number of $k$-Cliques in Sublinear Time, Fast recognition algorithms for classes of partial cubes, Querying relational event graphs using colored range searching data structures, Fast maximal cliques enumeration in sparse graphs, Bounds and algorithms for graph trusses, Positional Dominance: Concepts and Algorithms, Querying Relational Event Graphs Using Colored Range Searching Data Structures, Connectivity of plane triangulations, Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs, Online parameterized dictionary matching with one gap, Are unique subgraphs not easier to find?, Extended dynamic subgraph statistics using \(h\)-index parameterized data structures, Online recognition of dictionary with one gap, Finding and counting small induced subgraphs efficiently, Listing Maximal Subgraphs Satisfying Strongly Accessible Properties, Planar orientations with low out-degree and compaction of adjacency matrices, A Constructive Arboricity Approximation Scheme, Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms, Efficient algorithms for subgraph listing, Forests, frames, and games: Algorithms for matroid sums and applications, Listing Maximal Independent Sets with Minimal Space and Bounded Delay, A new decomposition technique for maximal clique enumeration for sparse graphs, Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph, An efficient exact algorithm for triangle listing in large graphs, Characterizing and recognizing 4-map graphs, Finding and counting given length cycles, Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs, Maximum cardinality neighbourly sets in quadrilateral free graphs, Embedding-preserving rectangle visibility representations of nonplanar graphs, Main-memory triangle computations for very large (sparse (power-law)) graphs, Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs, Theoretical underpinnings for maximal clique enumeration on perturbed graphs, Curve-constrained drawings of planar graphs, Parameterized aspects of triangle enumeration, On triangulating planar graphs under the four-connectivity constraint, Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search, On the characteristic polynomial of the power of a path., Octagonal drawings of plane graphs with prescribed face areas, Counting Subgraphs in Relational Event Graphs, An improved upper bound on maximal clique listing via rectangular fast matrix multiplication, Faster algorithms for counting subgraphs in sparse graphs, Unnamed Item, Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection, On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms, Clique Counting in MapReduce, Why Do Simple Algorithms for Triangle Enumeration Work in the Real World?, The Communication Complexity of Set Intersection and Multiple Equality Testing, An efficient parallel graph edge matching algorithm and its applications, Domination problems on P5-free graphs, Time Windowed Data Structures for Graphs, Unique subgraphs are not easier to find, Finding squares and rectangles in sets of points, An efficient algorithm for 1-dimensional (Persistent) path homology, Approximation algorithms for clique transversals on some graph classes, The maximum clique problem, Counting cliques in 1-planar graphs, A comparative study of dictionary matching with gaps: limitations, techniques and challenges
