Listing subgraphs by Cartesian decomposition

DOI10.4230/LIPICS.MFCS.2018.84MaRDI QIDQ5005188zbMATH OpenFDO

Authors Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, Luca Versari

Publication date 4 August 2021

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2018.84

zbMATH Keywords

constant delaygraph algorithmslistingminimum spanning trees

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Listing all the minimum spanning trees in an undirected graph
• scientific article; zbMATH DE number 177570
• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• An algorithm for the enumeration of spanning trees
• Counting Minimum Weight Spanning Trees

Cites work

• A flexible algorithm for generating all the spanning trees in undirected graphs
• Algorithm 457: finding all cliques of an undirected graph
• Algorithm Theory - SWAT 2004
• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
• Bibliography on Algorithms for Shortest Path, Shortest Spanning Tree, and Related Circuit Routing Problems (1956–1974)
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Counting and Enumeration Problems with Bounded Treewidth
• Decomposition by clique separators
• Efficient enumeration of bipartite subgraphs in graphs
• Efficient enumeration of maximal \(k\)-degenerate subgraphs in a chordal graph
• Efficient enumeration of subgraphs and induced subgraphs with bounded girth
• Enumerative applications of a decomposition for graphs and digraphs
• scientific article; zbMATH DE number 1080078 (Why is no real title available?)
• scientific article; zbMATH DE number 2176112 (Why is no real title available?)
• Introduction to algorithms.
• Listing Acyclic Orientations of Graphs with Single and Multiple Sources
• Listing acyclic subgraphs and subgraphs of bounded girth in directed graphs
• Listing all the minimum spanning trees in an undirected graph
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• Minimum-weight spanning tree algorithms. A survey and empirical study
• On enumerating all minimal solutions of feedback problems
• On generating all maximal independent sets
• On the History of the Minimum Spanning Tree Problem
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimal listing of cycles and st-paths in undirected graphs
• Parameterized algorithms
• Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences
• Reverse search for enumeration

Cited in

(1)

• Front Matter, Table of Contents, Preface, Conference Organization

Describes a project that uses

Uses Software

• Algorithm 457

This page was built for publication: Listing subgraphs by Cartesian decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5005188)