An algebraic theory of graph reduction
DOI10.1145/174147.169807zbMATH Open0795.68156OpenAlexW2018876684MaRDI QIDQ4285634FDOQ4285634
Authors: Stefan Arnborg, Andrzej Proskurowski, Detlef Seese, Bruno Courcelle 
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
Recommendations
- scientific article; zbMATH DE number 177426
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths
- Reduction algorithms for graphs of small treewidth
- scientific article; zbMATH DE number 219268
treewidthmonadic second-order logicgraph algebragraph reductiongraph rewritingregular set of graphsterminating reduction rules
Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)
Cited In (51)
- A polynomial-time algorithm for finding total colorings of partial \(k\)-trees
- Title not available (Why is that?)
- Kernelization: new upper and lower bound techniques
- A Retrospective on (Meta) Kernelization
- Decomposability helps for deciding logics of knowledge and belief
- I/O-efficient algorithms for graphs of bounded treewidth
- On the algorithmic effectiveness of digraph decompositions and complexity measures
- A parallel algorithm for edge-coloring partial k-trees
- Treewidth-two graphs as a free algebra
- Finite integer index of pathwidth and treewidth
- Constructive linear time algorithms for branchwidth
- An algorithm for transitive reduction of an acyclic graph
- Monoidal Width: Capturing Rank Width
- Parallel algorithms with optimal speedup for bounded treewidth
- A new reduction rule for the connection graph proof procedure
- Basic notions of universal algebra for language theory and graph grammars
- Canonical representations of partial 2- and 3-trees
- Algorithms for finding distance-edge-colorings of graphs
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
- Title not available (Why is that?)
- A partial k-arboretum of graphs with bounded treewidth
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- Kernelization -- preprocessing with a guarantee
- Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants
- Equivalent definitions of recognizability for sets of graphs of bounded tree-width
- Upper bounds to the clique width of graphs
- Improving spanning trees by upgrading nodes
- Line graphs of bounded clique-width
- The reduction of graph families closed under contraction
- Title not available (Why is that?)
- A method of graph reduction and its applications
- Listing all potential maximal cliques of a graph
- Meta-kernelization using well-structured modulators
- The recognizability of sets of graphs is a robust property
- Finding edge-disjoint paths in partial k-trees
- Improved self-reduction algorithms for graphs with bounded treewidth
- Graph Transformation in Constant Time
- Title not available (Why is that?)
- \(k\)-best solutions of MSO problems on tree-decomposable graphs
- Explicit linear kernels for packing problems
- On the reduction of Yutsis graphs
- On \(\tau\)-adic representations of integers
- Reduction algorithms for graphs of small treewidth
- Reduction algorithms for constructing solutions in graphs with small treewidth
- Tree-edges deletion problems with bounded diameter obstruction sets
- A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths
- Title not available (Why is that?)
- Hitting forbidden minors: approximation and kernelization
- Fixed-parameter tractability of treewidth and pathwidth
This page was built for publication: An algebraic theory of graph reduction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4285634)
