Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families

From MaRDI portal

Publication:1186787

Jump to:navigation, search

DOI10.1007/BF01758777zbMath0753.05062MaRDI QIDQ1186787

R. Gary Parker, Richard B. Borie, Craig A. Tovey

Publication date: 28 June 1992

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

predicate calculus linear-time algorithms decomposition tree automatic algorithm generation recursive graph class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Classical first-order logic (03B10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Safe separators for treewidth, A graph approximation heuristic for the vertex cover problem on planar graphs, Star colouring of bounded degree graphs and regular graphs, Compactors for parameterized counting problems, A Retrospective on (Meta) Kernelization, Improved self-reduction algorithms for graphs with bounded treewidth, A recurrence template for several parameters in series-parallel graphs, Regularity and locality in \(k\)-terminal graphs, A polynomial time algorithm to compute the connected treewidth of a series-parallel graph, Tree-edges deletion problems with bounded diameter obstruction sets, A polynomial time algorithm for strong edge coloring of partial \(k\)-trees, Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs, On Halin subgraphs and supergraphs, A parallel algorithm for edge-coloring partial k-trees, Parametric problems on graphs of bounded tree-width, Optimal parametric search on graphs of bounded tree-width, Regular-factors in the complements of partial k-trees, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, Practical algorithms on partial k-trees with an application to domination-like problems, Recognizability equals definability for graphs of bounded treewidth and bounded chordality, Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs, A general framework for path convexities, The parameterised complexity of list problems on graphs of bounded treewidth, The complexity of restricted star colouring, Algorithmic uses of the Feferman-Vaught theorem, Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees, Sparse obstructions for minor-covering parameters, On interval routing schemes and treewidth, Kernel bounds for path and cycle problems, Optimization problems in dotted interval graphs, Grouped domination parameterized by vertex cover, twin cover, and beyond, The firebreak problem, Large Induced Subgraphs via Triangulations and CMSO, Tangle bases: Revisited, Grouped domination parameterized by vertex cover, twin cover, and beyond, Convex Independence in Permutation Graphs, Tree-width and the monadic quantifier hierarchy., The complexity of power indexes with graph restricted coalitions, Dynamic algorithms for graphs with treewidth 2, On the complexity of some colorful problems parameterized by treewidth, Hardness transitions and uniqueness of acyclic colouring, Reduction algorithms for constructing solutions in graphs with small treewidth, Extended MSO model checking via small vertex integrity, Unnamed Item, Branch decomposition heuristics for linear matroids, Confronting intractability via parameters, On minimum dominating sets with minimum intersection, Practical algorithms for MSO model-checking on tree-decomposable graphs, A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs, Algorithms for recognition of regular properties and decomposition of recursive graph families, Algorithms for finding distance-edge-colorings of graphs, Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques, Reducing CMSO model checking to highly connected graphs, Explicit linear kernels for packing problems, NP-hard graph problems and boundary classes of graphs, Parallel algorithms with optimal speedup for bounded treewidth, On domination and reinforcement numbers in trees, A branch-and-price-and-cut method for computing an optimal bramble, Monadic second-order evaluations on tree-decomposable graphs, A short cut to optimal sequences, Parameterized complexity of the spanning tree congestion problem, Complexity of path-forming games, Branch-width, parse trees, and monadic second-order logic for matroids., Bounded treewidth as a key to tractability of knowledge representation and reasoning, A meta-theorem for distributed certification, Clique-perfectness of complements of line graphs, A linear‐time algorithm for broadcast domination in a tree, A note on trees, tables, and algorithms, Unnamed Item, The edge-disjoint paths problem is NP-complete for series-parallel graphs, Hitting Forbidden Minors: Approximation and Kernelization, Two strikes against perfect phylogeny, Width, depth, and space: tradeoffs between branching and dynamic programming, An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width, Clique-perfectness of complements of line graphs, Bidimensionality and Kernels, All structured programs have small tree width and good register allocation, A partial k-arboretum of graphs with bounded treewidth, Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques, Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth, On minimum cuts and the linear arrangement problem, Dynamic algorithms for graphs of bounded treewidth, Kernelization: New Upper and Lower Bound Techniques, The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, A meta-theorem for distributed certification, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Reduction algorithms for graphs of small treewidth, Unnamed Item, Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions, Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable, Tree polytope on 2-trees

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1186787&oldid=12055482"