Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
From MaRDI portal
Publication:1062758
DOI10.1007/BF01934985zbMath0573.68018MaRDI QIDQ1062758
Publication date: 1985
Published in: BIT (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to computer science (68-02)
Related Items (only showing first 100 items - show all)
Optimal parallel shortest paths in small treewidth digraphs ⋮ NC-algorithms for graphs with small treewidth ⋮ Fugitive-search games on graphs and related parameters ⋮ The longest common subsequence problem for sequences with nested arc annotations. ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Improved self-reduction algorithms for graphs with bounded treewidth ⋮ Regularity and locality in \(k\)-terminal graphs ⋮ A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ Treewidth of cocomparability graphs and a new order-theoretic parameter ⋮ Degree-constrained decompositions of graphs: Bounded treewidth and planarity ⋮ Tree-decompositions with bags of small diameter ⋮ Between treewidth and clique-width ⋮ On the Equivalence among Problems of Bounded Width ⋮ An asymptotic analysis of labeled and unlabeled \(k\)-trees ⋮ The pathwidth and treewidth of cographs ⋮ Canonical representations of partial 2-and 3-trees ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ Network-based heuristics for constraint-satisfaction problems ⋮ Boxicity and treewidth ⋮ A logical approach to efficient Max-SAT solving ⋮ Graph decompositions and tree automata in reasoning with uncertainty ⋮ Linear time algorithms for NP-hard problems restricted to partial k- trees ⋮ Treewidth for graphs with small chordality ⋮ Triangulating graphs without asteroidal triples ⋮ A decomposition algorithm for network reliability evaluation ⋮ Algebraic approach to fasciagraphs and rotagraphs ⋮ The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing ⋮ Complexity of Finding Embeddings in a k-Tree ⋮ Locating a robber with multiple probes ⋮ Decomposability helps for deciding logics of knowledge and belief ⋮ Efficient enumeration of all minimal separators in a graph ⋮ Local and global relational consistency ⋮ Fugitive-search games on graphs and related parameters ⋮ Triangulating multitolerance graphs ⋮ The firebreak problem ⋮ Tangle bases: Revisited ⋮ On switching classes, NLC-width, cliquewidth and treewidth ⋮ Portfolios in stochastic local search: efficiently computing most probable explanations in Bayesian networks ⋮ Splitting a graph into disjoint induced paths or cycles. ⋮ Decomposing a relation into a tree of binary relations ⋮ Forbidden minors characterization of partial 3-trees ⋮ Unnamed Item ⋮ How to compute digraph width measures on directed co-graphs ⋮ DAG-based attack and defense modeling: don't miss the forest for the attack trees ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ On permuted super-secondary structures of transmembrane \(\beta\)-barrel proteins ⋮ Treewidth and pathwidth of permutation graphs ⋮ Algorithms for recognition of regular properties and decomposition of recursive graph families ⋮ Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering ⋮ Unifying tree decompositions for reasoning in graphical models ⋮ Partition-based logical reasoning for first-order and propositional theories ⋮ Temporal constraint networks ⋮ LP Formulations for Polynomial Optimization Problems ⋮ Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families ⋮ A simple linear-time algorithm for finding path-decompositions of small width ⋮ On the max min vertex cover problem ⋮ Shortest path queries in digraphs of small treewidth ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Canonical representations of partial 2- and 3-trees ⋮ Precoloring extension. I: Interval graphs ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Structure identification in relational data ⋮ Treewidth computations. I: Upper bounds ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ General vertex disjoint paths in series-parallel graphs ⋮ Hypertree decompositions and tractable queries ⋮ Complexity of path-forming games ⋮ Connectivity of the graph induced by contractible edges of a \(k\)-tree ⋮ Treewidth computations. II. Lower bounds ⋮ A sufficiently fast algorithm for finding close to optimal clique trees ⋮ Topological parameters for time-space tradeoff ⋮ Girth and treewidth ⋮ Bounded treewidth as a key to tractability of knowledge representation and reasoning ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ The basic algorithm for pseudo-Boolean programming revisited ⋮ Two strikes against perfect phylogeny ⋮ A spectral lower bound for the treewidth of a graph and its consequences ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited ⋮ AND/OR search spaces for graphical models ⋮ Triangulating graphs with few \(P_4\)'s ⋮ On problems without polynomial kernels ⋮ Graph limits of random graphs from a subset of connected k‐trees ⋮ Comparing linear width parameters for directed graphs ⋮ Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs ⋮ Generating irregular partitionable data structures ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ Dynamic programming for graphs on surfaces ⋮ An algorithm for the Tutte polynomials of graphs of bounded treewidth ⋮ On the Tree-Width of Planar Graphs ⋮ Surfaces, tree-width, clique-minors, and partitions ⋮ Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs ⋮ On some optimization problems on \(k\)-trees and partial \(k\)-trees ⋮ Counting \(H-\)colorings of partial \(k-\)trees ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimization by Simulated Annealing
- Decomposition by clique separators
- An algorithm for finding clique cut-sets
- Complement reducible graphs
- On simple characterizations of k-trees
- Topology of series-parallel networks
- Triangulated graphs and the elimination process
- Nonserial dynamic programming
- Steiner trees, partial 2–trees, and minimum IFI networks
- Reduced State EnumerationߞAnother Algorithm for Reliability Evaluation
- Dynamic Programming is Optimal for Nonserial Optimization Problems
- Linear-time computability of combinatorial problems on series-parallel graphs
- Computing the Minimum Fill-In is NP-Complete
- Computing the Reliability of Complex Networks
- Complexity Results for Bandwidth Minimization
- Synthesizing constraint expressions
- A Computing Procedure for Quantification Theory
- Properties and characterizations of k ‐trees
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- The NP-completeness column: An ongoing guide
This page was built for publication: Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
