An algebraic theory of graph reduction
From MaRDI portal
Publication:4285634
DOI10.1145/174147.169807zbMath0795.68156MaRDI QIDQ4285634
Andrzej Proskurowski, Bruno Courcelle, Stefan Arnborg, 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
monadic second-order logic; treewidth; graph rewriting; graph algebra; graph reduction; regular set of graphs; terminating reduction rules
68R10: Graph theory (including graph drawing) in computer science
68Q42: Grammars and rewriting systems
Related Items
Equivalent definitions of recognizability for sets of graphs of bounded tree-width, The edge-disjoint paths problem is NP-complete for series-parallel graphs, Basic notions of universal algebra for language theory and graph grammars, I/O-efficient algorithms for graphs of bounded treewidth, On \(\tau\)-adic representations of integers, A polynomial algorithm testing partial confluence of basic semi-Thue systems, Canonical representations of partial 2- and 3-trees, A partial k-arboretum of graphs with bounded treewidth, Improved self-reduction algorithms for graphs with bounded treewidth, Listing all potential maximal cliques of a graph, Reduction algorithms for graphs of small treewidth, Algorithms for vertex-partitioning problems on graphs with fixed clique-width., Improving spanning trees by upgrading nodes, Upper bounds to the clique width of graphs, Tree-edges deletion problems with bounded diameter obstruction sets, Algorithms for finding distance-edge-colorings of graphs, Line graphs of bounded clique-width, The recognizability of sets of graphs is a robust property, Kernelization: New Upper and Lower Bound Techniques
