An algebraic theory of graph reduction

DOI10.1145/174147.169807zbMath0795.68156OpenAlexW2018876684MaRDI QIDQ4285634

Andrzej Proskurowski, Stefan Arnborg, Bruno Courcelle, Detlef Seese

Publication date: 11 September 1994

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.414.3347

zbMATH Keywords

monadic second-order logictreewidthgraph rewritinggraph algebragraph reductionregular set of graphsterminating reduction rules

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)

Related Items

Algorithms for vertex-partitioning problems on graphs with fixed clique-width. ⋮ A Retrospective on (Meta) Kernelization ⋮ Improved self-reduction algorithms for graphs with bounded treewidth ⋮ I/O-efficient algorithms for graphs of bounded treewidth ⋮ Tree-edges deletion problems with bounded diameter obstruction sets ⋮ A parallel algorithm for edge-coloring partial k-trees ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Constructive linear time algorithms for branchwidth ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Finite Integer Index of Pathwidth and Treewidth ⋮ Meta-kernelization using well-structured modulators ⋮ Decomposability helps for deciding logics of knowledge and belief ⋮ Monoidal Width: Capturing Rank Width ⋮ Reduction algorithms for constructing solutions in graphs with small treewidth ⋮ Unnamed Item ⋮ Improving spanning trees by upgrading nodes ⋮ On the algorithmic effectiveness of digraph decompositions and complexity measures ⋮ Equivalent definitions of recognizability for sets of graphs of bounded tree-width ⋮ Algorithms for finding distance-edge-colorings of graphs ⋮ Upper bounds to the clique width of graphs ⋮ Line graphs of bounded clique-width ⋮ Explicit linear kernels for packing problems ⋮ Basic notions of universal algebra for language theory and graph grammars ⋮ Parallel algorithms with optimal speedup for bounded treewidth ⋮ A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths ⋮ Canonical representations of partial 2- and 3-trees ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Unnamed Item ⋮ The edge-disjoint paths problem is NP-complete for series-parallel graphs ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On \(\tau\)-adic representations of integers ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ The recognizability of sets of graphs is a robust property ⋮ Bicriteria Network Design Problems ⋮ A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES ⋮ Reduction algorithms for graphs of small treewidth ⋮ Listing all potential maximal cliques of a graph