Graph minors. II. Algorithmic aspects of tree-width
From MaRDI portal
Publication:3751592
DOI10.1016/0196-6774(86)90023-4zbMath0611.05017OpenAlexW2029448190MaRDI QIDQ3751592
Publication date: 1986
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(86)90023-4
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items
Disconnected matchings, Clustered 3-colouring graphs of bounded degree, Bounding the search number of graph products, On the pathwidth of hyperbolic 3-manifolds, Computing Bond Types in Molecule Graphs, Structure of Graphs with Locally Restricted Crossings, Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts, Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates, Principled deep neural network training through linear programming, Spined categories: generalizing tree-width beyond graphs, The firebreak problem, Treelength of series-parallel graphs, Immunization in the threshold model: a parameterized complexity study, Monoidal Width, On the complexity of the storyplan problem, The complexity of learning minor closed graph classes, Minimum <scp>color‐degree</scp> perfect b‐matchings, Optimal parallel shortest paths in small treewidth digraphs, Public goods games in directed networks, Augmenting graphs to minimize the radius, Graphs of linear growth have bounded treewidth, On Interval Routing Schemes and treewidth, Shallow Minors, Graph Products, and Beyond-Planar Graphs, On the complexity of the storyplan problem, Dynamic algorithms for graphs with treewidth 2, Excluding a planar matching minor in bipartite graphs, Treewidth versus clique number. II: Tree-independence number, Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs, Spanning trees with few branch vertices in graphs of bounded neighborhood diversity, Monoidal Width: Capturing Rank Width, Stability, vertex stability, and unfrozenness for special graph classes, Weighted connected matchings, Unnamed Item, On the parameterized complexity of s-club cluster deletion problems, On the parameterized complexity of \(s\)-club cluster deletion problems, Efficient interprocedural data-flow analysis using treedepth and treewidth, General space-time tradeoffs via relational queries, Recognizing map graphs of bounded treewidth, On integer linear programs for treewidth based on perfect elimination orderings, Treewidth of the \(q\)-Kneser graphs, A lower bound for treewidth and its consequences, Tree-width and path-width of comparability graphs of interval orders, Bounded tree-width and LOGCFL, On reduction algorithms for graphs with small treewidth, Reduction algorithms for constructing solutions in graphs with small treewidth, Locating Eigenvalues of Symmetric Matrices - A Survey, Induced subgraphs and tree decompositions V. one neighbor in a hole, Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs, An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth, Eulerian Spaces, NC-algorithms for graphs with small treewidth, A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs, Unnamed Item, Minimum size tree-decompositions, Locating Facilities on a Network to Minimize Their Average Service Radius, Minimum size tree-decompositions, A 3-approximation for the pathwidth of Halin graphs, The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth., An algorithm for simultaneous backbone threading and side-chain packing, The complexity of broadcasting in planar and decomposable graphs, A Practical Approach to Courcelle's Theorem, The pagenumber of \(k\)-trees is \(O(k)\), To Approximate Treewidth, Use Treelength!, Approximation algorithms for maximum two-dimensional pattern matching, Power indices and easier hard problems, Linear ordering based MIP formulations for the vertex separation or pathwidth problem, Finding cut-vertices in the square roots of a graph, Constructing tree decompositions of graphs with bounded gonality, Constructing tree decompositions of graphs with bounded gonality, Clique-width of point configurations, Recognizing \(k\)-clique extendible orderings, Clique-perfectness of complements of line graphs, Heuristic and metaheuristic methods for computing graph treewidth, Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited, Disconnected matchings, On the treewidth of random geometric graphs and percolated grids, AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH, FINDING SMALLEST SUPERTREES UNDER MINOR CONTAINMENT, Uniform Constraint Satisfaction Problems and Database Theory, Tree decompositions and social graphs, Unnamed Item, Unnamed Item, Defective Coloring on Classes of Perfect Graphs, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth, On Treewidth and Related Parameters of Random Geometric Graphs, A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators, Algorithms, Complexity, and Hans, Algorithms and Complexity for Turaev-Viro Invariants, A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs, Provenance Circuits for Trees and Treelike Instances, Sequential and parallel algorithms for embedding problems on classes of partial k-trees, Community Structure Inspired Algorithms for SAT and #SAT, The pathwidth and treewidth of cographs, 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, The Birth and Early Years of Parameterized Complexity, A Basic Parameterized Complexity Primer, 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, On the k-rainbow domination in graphs with bounded tree-width, How to Use Spanning Trees to Navigate in Graphs, Target Set Selection in Dense Graph Classes, Decontamination of hypercubes by mobile agents, Unnamed Item, Unnamed Item, MAXIMUM INDEPENDENT, MINIMALLY REDUNDANT SETS IN SERIES-PARALLEL GRAPHS, Transforming graph states using single-qubit operations, Unnamed Item, The word problem for free adequate semigroups, Recognizability equals definability for partial k-paths, Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs, Enumerating graph embeddings and partial-duals by genus and Euler genus, Deterministic Algorithms for the Independent Feedback Vertex Set Problem, Algorithmic Applications of Tree-Cut Width, Decomposability helps for deciding logics of knowledge and belief, Efficient algorithms for solving systems of linear equations and path problems, Complexity and Algorithms for Well-Structured k-SAT Instances, Inference and learning in probabilistic logic programs using weighted Boolean formulas, Graph coloring with no large monochromatic components, From Invariants to Canonization in Parallel, Low Polynomial Exclusion of Planar Graph Patterns, Mineurs d'arbres avec racines, Monotonicity of Non-deterministic Graph Searching, The Clique-Width of Tree-Power and Leaf-Power Graphs, On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints, Track Layout Is Hard, Unnamed Item, Automata-based Representations for Infinite Graphs, Finite Automata, Digraph Connectivity, and Regular Expression Size, Dynamic Management of Heuristics for Solving Structured CSPs, Parameters Tied to Treewidth, Provably Shorter Regular Expressions from Deterministic Finite Automata, Solving Graph Problems via Potential Maximal Cliques, Parameterized Algorithms for Book Embedding Problems, Coalition formation in social environments with logic-based agents1, Orthogonal Tree Decompositions of Graphs, Thread Graphs, Linear Rank-Width and Their Algorithmic Applications, Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension, LP Formulations for Polynomial Optimization Problems, Decomposing SAT Instances with Pseudo Backbones, Parameterized Leaf Power Recognition via Embedding into Graph Products, Fifty years of the spectrum problem: survey and new results, Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$, Shortest path queries in digraphs of small treewidth, Solution to König's Graph Embedding Problem, APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM, Vertex-Bipartition Method for Colouring Minor-Closed Classes of Graphs, Unnamed Item, A Quartic Kernel for Pathwidth-One Vertex Deletion, An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion, Are There Any Good Digraph Width Measures?, The Effect of Planarization on Width, A $c^k n$ 5-Approximation Algorithm for Treewidth, Optimizing Answer Set Computation via Heuristic-Based Decomposition, Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints, A Local Search Algorithm for Branchwidth, Line planning, path constrained network flow and inapproximability, Strongly Sublinear Separators and Polynomial Expansion, Control of Some Graph Invariants in Dynamic Routing, Unnamed Item, Bounds on vertex colorings with restrictions on the union of color classes, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs, An Efficient Partitioning Oracle for Bounded-Treewidth Graphs, On the Complexity of Computing Treebreadth, Faster Computation of Path-Width, Encoding Treewidth into SAT, A Single Approach to Decide Chase Termination on Linear Existential Rules, Lean Tree-Cut Decompositions: Obstructions and Algorithms, Finding Paths in Grids with Forbidden Transitions, Improved Bounds for the Excluded-Minor Approximation of Treedepth, Exploiting Separators for Guiding VNS, Dynamic algorithms for graphs of bounded treewidth, On Digraph Width Measures in Parameterized Algorithmics, Positive-Instance Driven Dynamic Programming for Treewidth., Contraction-Bidimensionality of Geometric Intersection Graphs, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Augmenting Outerplanar Graphs to Meet Diameter Requirements, Disjoint Paths—A Survey, Well-Quasi-Ordering Infinite Graphs with Forbidden Finite Planar Minor, Perfect edge domination and efficient edge domination in graphs, Algorithms for vertex-partitioning problems on graphs with fixed clique-width., Graph minors. V. Excluding a planar graph, A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Improved self-reduction algorithms for graphs with bounded treewidth, The nonexistence of reduction rules giving an embedding into a \(k\)-tree, \(k\)-NLC graphs and polynomial algorithms, Eigenvalue location in graphs of small clique-width, Obstructions to a small hyperbolicity in Helly graphs, Induced and weak induced arboricities, Fork-decompositions of matroids, A polynomial time algorithm for strong edge coloring of partial \(k\)-trees, Rooted routing in the plane, Grids and their minors, On the complexity of rainbow coloring problems, Generalized coloring for tree-like graphs, Linear time algorithms for NP-hard problems restricted to partial k- trees, Treewidth for graphs with small chordality, Characterizations and algorithmic applications of chordal graph embeddings, Algebraic approach to fasciagraphs and rotagraphs, Minimum self-repairing graphs, Secluded connectivity problems, The complexity of broadcasting in planar and decomposable graphs, Triangulating multitolerance graphs, Improved Steiner tree algorithms for bounded treewidth, Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width., Branch-width and Rota's conjecture, Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees, Approximation algorithms via contraction decomposition, Approximating the treewidth of AT-free graphs., Splitting a graph into disjoint induced paths or cycles., Structured probabilistic inference, Combining restarts, nogoods and bag-connected decompositions for solving csps, Chordal embeddings of planar graphs, Trimming of graphs, with application to point labeling, On minimum dominating sets with minimum intersection, Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time, Track layouts, layered path decompositions, and leveled planarity, Decomposing infinite graphs, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, On the complexity of computing treebreadth, Algorithm to find a maximum 2-packing set in a cactus, The critical node detection problem in networks: a survey, A branch-and-price-and-cut method for computing an optimal bramble, Precoloring extension. I: Interval graphs, On the complexity of finding iso- and other morphisms for partial \(k\)- trees, Diagonalization, uniformity, and fixed-point theorems, On tradeoffs between width- and fill-like graph parameters, An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion, Towards fixed-parameter tractable algorithms for abstract argumentation, Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts, General vertex disjoint paths in series-parallel graphs, Disjoint paths in sparse graphs, On the power of structural decompositions of graph-based representations of constraint problems, Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs, Packing disjoint cycles over vertex cuts, A little statistical mechanics for the graph theorist, Combining CP and ILP in a tree decomposition of bounded height for the sum colouring problem, On listing, sampling, and counting the chordal graphs with edge constraints, Querying linguistic treebanks with monadic second-order logic in linear time, Efficient frequent connected subgraph mining in graphs of bounded tree-width, Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization, On the maximum cardinality search lower bound for treewidth, On compact and efficient routing in certain graph classes, Clique-width of graphs defined by one-vertex extensions, Monotony properties of connected visible graph searching, Fixed-parameter algorithms for protein similarity search under mRNA structure constraints, Representing graphs as the intersection of cographs and threshold graphs, On \textsf{NC} algorithms for problems on bounded rank-width graphs, Beating treewidth for average-case subgraph isomorphism, Tree-width, path-width, and cutwidth, A spectral lower bound for the treewidth of a graph and its consequences, An approximation algorithm for computing longest paths., Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction, Approximating the maximum clique minor and some subgraph homeomorphism problems, On tree-partition-width, Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms, A partial k-arboretum of graphs with bounded treewidth, The NLC-width and clique-width for powers of graphs of bounded tree-width, Computational properties of argument systems satisfying graph-theoretic constraints, Characterizing multiterminal flow networks and computing flows in networks of small treewidth, Generating irregular partitionable data structures, Algorithms for generalized vertex-rankings of partial k-trees, Computational study on planar dominating set problem, Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth, Pathwidth of cubic graphs and exact algorithms, A comparison of structural CSP decomposition methods, Graph minors. I. Excluding a forest, Surfaces, tree-width, clique-minors, and partitions, High-girth graphs avoiding a minor are nearly bipartite, On matroids of branch-width three., Forests, colorings and acyclic orientations of the square lattice, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., On hyperedge replacement and BNLC graph grammars, On the pathwidth of chordal graphs, On some optimization problems on \(k\)-trees and partial \(k\)-trees, Counting \(H-\)colorings of partial \(k-\)trees, Fixed-parameter complexity in AI and nonmonotonic reasoning, Listing all potential maximal cliques of a graph, Minimal triangulations of graphs: a survey, The treewidth and pathwidth of hypercubes, Structural tractability of counting of solutions to conjunctive queries, On computational complexity of graph inference from counting, On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity, A coloring problem for weighted graphs, Acyclic coloring parameterized by directed clique-width, Contraction bidimensionality of geometric intersection graphs, Fully polynomial-time approximation schemes for time-cost tradeoff problems in series-parallel project networks, Approximating the pathwidth of outerplanar graphs, On the complexity of constrained Nash equilibria in graphical games, Contraction obstructions for connected graph searching, Parameterized dominating set problem in chordal graphs: Complexity and lower bound, Approximate tree decompositions of planar graphs in linear time, Collective tree spanners in graphs with bounded parameters, Approximation algorithms for treewidth, New analysis and computational study for the planar connected dominating set problem, Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs, Combinatorics of TCP reordering, On zeros of the characteristic polynomial of matroids of bounded tree-width, Vertex-minors, monadic second-order logic, and a conjecture by Seese, Online promise problems with online width metrics, A generalization of Spira's theorem and circuits with small segregators or separators, Characterizing width two for variants of treewidth, Courcelle's theorem for triangulations, Exact algorithms and applications for tree-like Weighted Set Cover, A local characterization of bounded clique-width for line graphs, Characterizations for restricted graphs of NLC-width 2, Graphs with bounded tree-width and large odd-girth are almost bipartite, Some recent progress and applications in graph minor theory, Weighted hypertree decompositions and optimal query plans, Achievable sets, brambles, and sparse treewidth obstructions, Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth, Tractable counting of the answers to conjunctive queries, Two characterisations of the minimal triangulations of permutation graphs, Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem, Courcelle's theorem -- a game-theoretic approach, Are there any good digraph width measures?, Sublinear separators, fragility and subexponential expansion, Graph classes with and without powers of bounded clique-width, On the complexity of the regenerator location problem treewidth and other parameters, The disjoint paths problem in quadratic time, Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs, On the treewidth of toroidal grids, Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs, Trimming weighted graphs of bounded treewidth, A faster polynomial-space algorithm for Max 2-CSP, On switching classes, NLC-width, cliquewidth and treewidth, A hybrid tractable class for non-binary CSPs, Computing bond orders in molecule graphs, Minesweeper on graphs, On shortest disjoint paths in planar graphs, Directed NLC-width, Most probable explanations in Bayesian networks: complexity and tractability, Treewidth governs the complexity of target set selection, On the algorithmic effectiveness of digraph decompositions and complexity measures, Treewidth lower bounds with brambles, Maximum \(k\)-splittable \(s, t\)-flows, An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs, Practical algorithms for MSO model-checking on tree-decomposable graphs, Monotonicity of non-deterministic graph searching, Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, Introduction to special issue on RNA, Rapid ab initio prediction of RNA pseudoknots via graph tree decomposition, A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs, Computing cooperative solution concepts in coalitional skill games, Algebraically grid-like graphs have large tree-width, Characterization of minimum cycle basis in weighted partial 2-trees, The inverse 1-maxian problem with edge length modification, The complexity of subgraph isomorphism for classes of partial k-trees, A simple linear-time algorithm for finding path-decompositions of small width, Characterization and complexity of uniformly nonprimitive labeled 2-structures, On the complexity of the multicut problem in bounded tree-width graphs and digraphs, Neighbourhood-width of trees, Linearity of grid minors in treewidth with applications through bidimensionality, Recognising \(k\)-connected hypergraphs in cubic time, The behavior of clique-width under graph operations and graph transformations, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, Efficient sets in partial \(k\)-trees, Peptide sequencing via graph path decomposition, Treewidth computations. I: Upper bounds, Hypertree decompositions and tractable queries, Connected graph searching in chordal graphs, Recent developments on graphs of bounded clique-width, On the complexity of some subgraph problems, Treewidth computations. II. Lower bounds, Minimum vertex cover in rectangle graphs, Logical aspects of Cayley-graphs: the group case, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time, Girth and treewidth, Upper and lower bounds for finding connected motifs in vertex-colored graphs, The treewidth of line graphs, On bounded-degree vertex deletion parameterized by treewidth, Quantitative graph theory: a new branch of graph theory and network science, On the complexity of reasoning about opinion diffusion under majority dynamics, Complexity of abstract argumentation under a claim-centric view, Parameterized leaf power recognition via embedding into graph products, Graph minors. III. Planar tree-width, The structure of the models of decidable monadic theories of graphs, Hybrid backtracking bounded by tree-decomposition of constraint networks, Augmenting weighted graphs to establish directed point-to-point connectivity, Treewidth of the generalized Kneser graphs, A new approach on locally checkable problems, Tree-decompositions with bags of small diameter, How to use spanning trees to navigate in graphs, Probabilistic logic with independence, A logical approach to multicut problems, Spanners for bounded tree-length graphs, Directed width parameters on semicomplete digraphs, Graph minors. IV: Tree-width and well-quasi-ordering, Tree-width and the Sherali-Adams operator, An improved planar graph product structure theorem, The relative clique-width of a graph, Parameterized complexity of immunization in the threshold model, A logic of reachable patterns in linked data-structures, Treewidth computation and extremal combinatorics, The rank-width of edge-coloured graphs, Space-efficient vertex separators for treewidth, Boundary classes for graph problems involving non-local properties, Rank-width: algorithmic and structural results, Parameterized analysis and crossing minimization problems, The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing, Helly-gap of a graph and vertex eccentricities, The tree-width of C, Layered separators in minor-closed graph classes with applications, A polynomial kernel for block graph deletion, On the vertex cover \(P_3\) problem parameterized by treewidth, Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?, Treewidth and gonality of glued grid graphs, On the thinness and proper thinness of a graph, On the computational complexity of the bipartizing matching problem, Fast exact algorithms for some connectivity problems parameterized by clique-width, Positive-instance driven dynamic programming for treewidth, Probabilistic and exact frequent subtree mining in graphs beyond forests, Computing partial hypergraphs of bounded width, Cops that surround a robber, FPT and kernelization algorithms for the induced tree problem, On fractional fragility rates of graph classes, On treewidth, separators and Yao's garbling, Parameterized algorithms for book embedding problems, Sketched representations and orthogonal planarity of bounded treewidth graphs, A computational-level explanation of the speed of goal inference, Reconfiguration of cliques in a graph, The theory of guaranteed search on graphs, Digraph width measures in parameterized algorithmics, Graphs of small rank-width are pivot-minors of graphs of small tree-width, Counting solutions to CSP using generating polynomials, How to compute digraph width measures on directed co-graphs, Classes of graphs with low complexity: the case of classes with bounded linear rankwidth, A note on sublinear separators and expansion, Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering, Partition-based logical reasoning for first-order and propositional theories, Line graphs of bounded clique-width, Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs, Visualizing SAT instances and runs of the DPLL algorithm, Efficient computation of the oriented chromatic number of recursively defined digraphs, New width parameters for SAT and \#SAT, The Potts model and the Tutte polynomial, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, On the complexity of connectivity in cognitive radio networks through spectrum assignment, Tree decomposition and discrete optimization problems: a survey, An exact method for graph coloring, On the colored Tutte polynomial of a graph of bounded treewidth, Tree-depth, subgraph coloring and homomorphism bounds, Optimization for first order Delaunay triangulations, Contiguous search problem in Sierpiński graphs, The basic algorithm for pseudo-Boolean programming revisited, Vertex disjoint paths on clique-width bounded graphs, The complexity of graph languages generated by hyperedge replacement, Treewidth, crushing and hyperbolic volume, Whither semantics?, The role of planarity in connectivity problems parameterized by treewidth, Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth, Tree-coloring problems of bounded treewidth graphs, On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines, Strong NP-hardness of AC power flows feasibility, On exteriority notions in book embeddings and treewidth, Using decomposition-parameters for QBF: mind the prefix!, Faster algorithms for quantitative verification in bounded treewidth graphs, Notes on graph product structure theory, Spanning tree constrained determinantal point processes are hard to (approximately) evaluate, Treewidth of graphs with balanced separations, Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth, Algorithms and complexity for Turaev-Viro invariants, Orthogonal planarity testing of bounded treewidth graphs, Comparing linear width parameters for directed graphs, Evaluating Datalog via tree automata and cycluits, On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem, Fast and parallel decomposition of constraint satisfaction problems, Exact algorithms for counting 3-colorings of graphs, The first order definability of graphs with separators via the Ehrenfeucht game, Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth, On the relationship between NLC-width and linear NLC-width, Backdoors to tractable answer set programming, Pure Nash equilibria in graphical games and treewidth, Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions, On the tree-depth and tree-width in heterogeneous random graphs, Non-deterministic graph searching in trees, A fixed-parameter algorithm for guarding 1.5D terrains, New limits of treewidth-based tractability in optimization
