Easy problems for tree-decomposable graphs
From MaRDI portal
Publication:3361904
DOI10.1016/0196-6774(91)90006-KzbMath0734.68073OpenAlexW2064796716MaRDI QIDQ3361904
Jens Lagergren, Stefan Arnborg, Detlef Seese
Publication date: 1991
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(91)90006-k
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Parameterized Complexity of $$(A,\ell )$$-Path Packing, Seeing Arboretum for the (partial k-) Trees, As Time Goes By: Reflections on Treewidth for Temporal Graphs, A Retrospective on (Meta) Kernelization, Sequential and parallel algorithms for embedding problems on classes of partial k-trees, A parallel algorithm for edge-coloring partial k-trees, Formal language constrained path problems, Testing superperfection of 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, Practical algorithms on partial k-trees with an application to domination-like problems, Complexity of the Packing Coloring Problem for Trees, A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata, Recognizable sets of graphs: equivalent definitions and closure properties, Graph decompositions and tree automata in reasoning with uncertainty, A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs, Inductive computations on graphs defined by clique-width expressions, Decomposability helps for deciding logics of knowledge and belief, Recognizable sets of graphs of bounded tree-width, Grouped domination parameterized by vertex cover, twin cover, and beyond, The firebreak problem, Tangle bases: Revisited, Grouped domination parameterized by vertex cover, twin cover, and beyond, On Interval Routing Schemes and treewidth, Deletion to scattered graph classes. I: Case of finite number of graph classes, Dynamic algorithms for graphs with treewidth 2, Treewidth versus clique number. II: Tree-independence number, Allocation of indivisible items with individual preference graphs, Unnamed Item, Graph burning and non-uniform \(k\)-centers for small treewidth, A lower bound for treewidth and its consequences, Bounded tree-width and LOGCFL, On reduction algorithms for graphs with small treewidth, Reduction algorithms for constructing solutions in graphs with small treewidth, Extended MSO model checking via small vertex integrity, Automata-based Representations for Infinite Graphs, An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth, Unnamed Item, Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs, Equivalent definitions of recognizability for sets of graphs of bounded tree-width, Finite automata as characterizations of minor closed tree families (extended abstract), The size of an intertwine, Reducing CMSO model checking to highly connected graphs, The Complexity of Finding Small Separators in Temporal Graphs, Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes, How to use the minimal separators of a graph for its chordal triangulation, A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths, An algorithm for simultaneous backbone threading and side-chain packing, The complexity of broadcasting in planar and decomposable graphs, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, A Practical Approach to Courcelle's Theorem, Non-Hyperbolicity of Random Graphs with Given Expected Degrees, A sufficiently fast algorithm for finding close to optimal clique trees, A linear‐time algorithm for broadcast domination in a tree, Unnamed Item, Unnamed Item, The edge-disjoint paths problem is NP-complete for series-parallel graphs, Unnamed Item, Two strikes against perfect phylogeny, Computations by fly-automata beyond monadic second-order logic, Constructing minimum changeover cost arborescenses in bounded treewidth graphs, Secure total domination in chain graphs and cographs, An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, Feedback edge sets in temporal graphs, Unnamed Item, Unnamed Item, Exploring the gap between treedepth and vertex cover through vertex integrity, Unnamed Item, Minimum eccentricity shortest path problem with respect to structural parameters, Exploring the gap between treedepth and vertex cover through vertex integrity, Treewidth of display graphs: bounds, brambles and applications, Unnamed Item, Dynamic algorithms for graphs of bounded treewidth, A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES, Network-Based Vertex Dissolution, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Unnamed Item, Unnamed Item, Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable, Monadic second-order definable graph transductions: a survey, An algorithmic metatheorem for directed treewidth, Safe separators for treewidth, Compatibility of unrooted phylogenetic trees is FPT, Trees, grids, and MSO decidability: from graphs to matroids, Compactors for parameterized counting problems, A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs, A coloring problem for weighted graphs, Improved self-reduction algorithms for graphs with bounded treewidth, The monadic second order logic of graphs. VI: On several representations of graphs by relational structures, \(k\)-NLC graphs and polynomial algorithms, Contraction bidimensionality of geometric intersection graphs, On the feedback vertex set polytope of a series-parallel graph, I/O-efficient algorithms for graphs of bounded treewidth, Parameterized complexity dichotomy for \textsc{Steiner Multicut}, Safe sets in graphs: graph classes and structural parameters, Approximate tree decompositions of planar graphs in linear time, Reduction rules for the maximum parsimony distance on phylogenetic trees, Deleting edges to restrict the size of an epidemic: a new application for treewidth, Approximation algorithms for treewidth, Courcelle's theorem for triangulations, Characterizations and algorithmic applications of chordal graph embeddings, Algorithmic uses of the Feferman-Vaught theorem, On interval routing schemes and treewidth, Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth, Converting triangulations to quadrangulations, Logical description of context-free graph languages, MSOL partitioning problems on graphs of bounded treewidth and clique-width, Kernel bounds for path and cycle problems, Effective computation of immersion obstructions for unions of graph classes, Splitting trees at vertices, The complexity of broadcasting in planar and decomposable graphs, Triangulating multitolerance graphs, Farrell polynomials on graphs of bounded tree width, Courcelle's theorem -- a game-theoretic approach, Are there any good digraph width measures?, Meta-kernelization with structural parameters, Practical algorithms for branch-decompositions of planar graphs, The complexity of two graph orientation problems, Tree-width and the monadic quantifier hierarchy., Decomposition width of matroids, The complexity of power indexes with graph restricted coalitions, Compact labelings for efficient first-order model-checking, On the complexity of some colorful problems parameterized by treewidth, Approximation of minimum weight spanners for sparse graphs, Linkless and flat embeddings in 3-space, Splitting a graph into disjoint induced paths or cycles., A combinatorial optimization algorithm for solving the branchwidth problem, Channel assignment on graphs of bounded treewidth, Paths of bounded length and their cuts: parameterized complexity and algorithms, On the directed full degree spanning tree problem, Combinatorial and computational aspects of graph packing and graph decomposition, On the complexity of core, kernel, and bargaining set, Guard games on graphs: keep the intruder out!, Confronting intractability via parameters, Maximum \(k\)-splittable \(s, t\)-flows, Cycle-maximal triangle-free graphs, Practical algorithms for MSO model-checking on tree-decomposable graphs, Algorithms for recognition of regular properties and decomposition of recursive graph families, A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs, Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}, Algorithms for decision problems in argument systems under preferred semantics, Basic notions of universal algebra for language theory and graph grammars, Characterization and complexity of uniformly nonprimitive labeled 2-structures, Solving some NP-complete problems using split decomposition, The monadic second-order logic of graphs. VII: Graphs as relational structures, Parameterized complexity of critical node cuts, Monadic second-order evaluations on tree-decomposable graphs, Efficient sets in partial \(k\)-trees, Partitioning graphs of supply and demand, Minimum dominating set of queens: a trivial programming exercise?, Complexity of path-forming games, Complexity of the packing coloring problem for trees, Monadic second-order model-checking on decomposable matroids, A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time, Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity, A survey of selected recent results on total domination in graphs, The complexity ecology of parameters: An illustration using bounded max leaf number, Approximability of partitioning graphs with supply and demand, Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width, Algorithms for unipolar and generalized split graphs, On the OBDD size for graphs of bounded tree- and clique-width, All structured programs have small tree width and good register allocation, Upper bounds on the size of obstructions and intertwines, Computational properties of argument systems satisfying graph-theoretic constraints, Characterizing multiterminal flow networks and computing flows in networks of small treewidth, The monadic second-order logic of graphs. XII: Planar graphs and planar maps, On minimum cuts and the linear arrangement problem, Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth, On the complexity of reasoning about opinion diffusion under majority dynamics, Complexity of abstract argumentation under a claim-centric view, A comparison of tree transductions defined by monadic second order logic and by attribute grammars, Parameterized leaf power recognition via embedding into graph products, An algorithm for the Tutte polynomials of graphs of bounded treewidth, A comparison of structural CSP decomposition methods, On the pathwidth of chordal graphs, NP-completeness of minimum spanner problems, Counting \(H-\)colorings of partial \(k-\)trees, On algorithms for (\(P_5\), gem)-free graphs, Complexity of the multilevel critical node problem, Algorithms for vertex-partitioning problems on graphs with fixed clique-width., Parameterized Complexity of Firefighting Revisited, Tree-edges deletion problems with bounded diameter obstruction sets, A polynomial time algorithm for strong edge coloring of partial \(k\)-trees, Provenance Circuits for Trees and Treelike Instances, Unnamed Item, A logical approach to multicut problems, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs, Tree-width and the Sherali-Adams operator, A logic of reachable patterns in linked data-structures, A general framework for path convexities, Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth, On the Satisfiability of Quantum Circuits of Small Treewidth, On some domination colorings of graphs, Boundary classes for graph problems involving non-local properties, Distance from triviality 2.0: hybrid parameterizations, On orthogonally guarding orthogonal polygons with bounded treewidth, Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues, The tree-width of C, Hitting forbidden subgraphs in graphs of bounded treewidth, On strongly connected digraphs with bounded cycle length, Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability, On the satisfiability of quantum circuits of small treewidth, An approval-based model for single-step liquid democracy, Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs, A Note on the Minimum H-Subgraph Edge Deletion, Large Induced Subgraphs via Triangulations and CMSO, Safe Sets in Graphs: Graph Classes and Structural Parameters, The multi-stripe travelling salesman problem, Polynomial kernels for hitting forbidden minors under structural parameterizations, Polynomial-time algorithms for special cases of the maximum confluent flow problem, A PTAS for the Cluster Editing Problem on Planar Graphs, Complexity and algorithms for recognizing polar and monopolar graphs, Fair allocation of indivisible items with conflict graphs, Path-contractions, edge deletions and connectivity preservation, Unnamed Item, Maximum packing for biconnected outerplanar graphs, Branch decomposition heuristics for linear matroids, Parameterized complexity of firefighting, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs, Algorithms for finding distance-edge-colorings of graphs, Upper bounds to the clique width of graphs, Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time, Counting linear extensions: parameterizations by treewidth, A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter, Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size, Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width, Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory, Algorithm to find a maximum 2-packing set in a cactus, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques, A branch-and-price-and-cut method for computing an optimal bramble, On compatibility and incompatibility of collections of unrooted phylogenetic trees, Complexity of minimum irreducible infeasible subsystem covers for flow networks, A short cut to optimal sequences, Tree decomposition and discrete optimization problems: a survey, Algorithmic meta-theorems for restrictions of treewidth, Planar graph bipartization in linear time, Two feedback problems for graphs with bounded tree-width, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, The complexity of finding small separators in temporal graphs, Querying linguistic treebanks with monadic second-order logic in linear time, Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees, Bounded treewidth as a key to tractability of knowledge representation and reasoning, A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs, Monadic Second Order Logic on Graphs with Local Cardinality Constraints, The complexity of frugal colouring, Fixed-parameter tractability results for full-degree spanning tree and its dual, Hitting Forbidden Minors: Approximation and Kernelization, Are There Any Good Digraph Width Measures?, Reducing graph transversals via edge contractions, Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth, New Results on the Complexity of the Max- and Min-Rep Problems, A unifying model for locally constrained spanning tree problems, Parameterized complexity of vertex colouring, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, A comparison of compatible, finite, and inductive graph properties, Bidimensionality and Kernels, Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks, A Slice Theoretic Approach for Embedding Problems on Digraphs, Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth, The complexity of the matching-cut problem for planar graphs and other graph classes, Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms, On the Directed Degree-Preserving Spanning Tree Problem, Bicriteria Network Design Problems, The monadic second-order logic of graphs. VIII: Orientations, Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds, Reduction algorithms for graphs of small treewidth, The complexity of the \(K_{n,n}\)-problem for node replacement graph languages, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions, On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs, Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs, The \(k\)-separator problem: polyhedra, complexity and approximation results, Shelah-Stupp's and Muchnik's iterations revisited, New limits of treewidth-based tractability in optimization, Parameterized complexity of \((A,\ell)\)-path packing
