Treewidth. Computations and approximations
From MaRDI portal
Publication:1338451
DOI10.1007/BFb0045375zbMath0825.68144OpenAlexW4213368513MaRDI QIDQ1338451
Publication date: 1 December 1994
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bfb0045375
Related Items
Parameterized Complexity of $$(A,\ell )$$-Path Packing ⋮ On the Parameterized Complexity of the Expected Coverage Problem ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ A Retrospective on (Meta) Kernelization ⋮ Fast Algorithms for Join Operations on Tree Decompositions ⋮ Rank-width of random graphs ⋮ Algorithms and Complexity for Turaev-Viro Invariants ⋮ Efficient Problem Solving on Tree Decompositions Using Binary Decision Diagrams ⋮ An Improvement of Reed’s Treewidth Approximation ⋮ Unnamed Item ⋮ Subexponential Time Algorithms for Finding Small Tree and Path Decompositions ⋮ Community Structure Inspired Algorithms for SAT and #SAT ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Mixed covering arrays on graphs of small treewidth ⋮ Unnamed Item ⋮ Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth ⋮ Bivariate Complexity Analysis of Almost Forest Deletion ⋮ Sum-of-Products with Default Values: Algorithms and Complexity Results ⋮ On the pathwidth of hyperbolic 3-manifolds ⋮ Computing Bond Types in Molecule Graphs ⋮ Independent sets in asteroidal triple-free graphs ⋮ On temporal graph exploration ⋮ Bisection of bounded treewidth graphs by convolutions ⋮ Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all? ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ Small Resolution Proofs for QBF using Dependency Treewidth ⋮ Metric Dimension of Bounded Width Graphs ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges ⋮ The connected critical node problem ⋮ Algorithms for Propositional Model Counting ⋮ Algebras for Tree Decomposable Graphs ⋮ Capacitated Domination and Covering: A Parameterized Perspective ⋮ A Logspace Algorithm for Partial 2-Tree Canonization ⋮ Parameterized complexity of envy-free resource allocation in social networks ⋮ Safe Sets in Graphs: Graph Classes and Structural Parameters ⋮ Parameterized complexity of computing maximum minimal blocking and hitting sets ⋮ Eulerian walks in temporal graphs ⋮ Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A PTAS for the Cluster Editing Problem on Planar Graphs ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ On computing the Hamiltonian index of graphs ⋮ Unnamed Item ⋮ On the Maximum Weight Minimal Separator ⋮ Networks on which hot-potato routing does not livelock ⋮ The Space Complexity of k-Tree Isomorphism ⋮ Fractional Edge Cover Number of Model RB ⋮ Linearizing Genomes: Exact Methods and Local Search ⋮ Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT ⋮ How to Cut a Graph into Many Pieces ⋮ How to use the minimal separators of a graph for its chordal triangulation ⋮ Tractable answer-set programming with weight constraints: bounded treewidth is not enough ⋮ Parameterized algorithms for the happy set problem ⋮ Unnamed Item ⋮ A sufficiently fast algorithm for finding close to optimal clique trees ⋮ Monadic Second Order Logic on Graphs with Local Cardinality Constraints ⋮ The HOMFLY-PT polynomial is fixed-parameter tractable ⋮ Unnamed Item ⋮ On the number of labeled graphs of bounded treewidth ⋮ Unnamed Item ⋮ A Quartic Kernel for Pathwidth-One Vertex Deletion ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Default logic and bounded treewidth ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ Graph isomorphism restricted by lists ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Parameterized complexity of conflict-free set cover ⋮ Minimum reload cost graph factors ⋮ Unnamed Item ⋮ Walking through waypoints ⋮ The complexity of tree partitioning ⋮ On giant components and treewidth in the layers model ⋮ Relating Structure and Power: Comonadic Semantics for Computational Resources ⋮ New Results for Network Pollution Games ⋮ Randomized rumor spreading in poorly connected small-world networks ⋮ On the tractability of covering a graph with 2-clubs ⋮ Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs ⋮ Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs ⋮ Parameterized Complexity of Discrete Morse Theory ⋮ Counting Perfect Matchings and the Switch Chain ⋮ Some Properties of Random Apollonian Networks ⋮ On the treewidth of random geometric graphs and percolated grids ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Valve Location Problem in Simple Network Topologies ⋮ Planar k-Path in Subexponential Time and Polynomial Space ⋮ The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ⋮ Unnamed Item ⋮ Quadratic Upper Bounds on the Erdős-Pósa Property for a Generalization of Packing and Covering Cycles ⋮ On Complexities of Minus Domination ⋮ Metric Dimension of Bounded Tree-length Graphs ⋮ On Treewidth and Related Parameters of Random Geometric Graphs ⋮ The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs ⋮ Perfect edge domination and efficient edge domination in graphs ⋮ A linear time algorithm to list the minimal separators of chordal graphs ⋮ Parameterized coloring problems on chordal graphs ⋮ A parameterized complexity view on collapsing \(k\)-cores ⋮ An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification ⋮ An edge variant of the Erdős-Pósa property ⋮ Structural parameterizations of clique coloring ⋮ I/O-efficient algorithms for graphs of bounded treewidth ⋮ \((1, j)\)-set problem in graphs ⋮ Safe sets in graphs: graph classes and structural parameters ⋮ Deleting edges to restrict the size of an epidemic: a new application for treewidth ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ Collective tree spanners in graphs with bounded parameters ⋮ Approximation algorithms for treewidth ⋮ Geometric representation of graphs in low dimension using axis parallel boxes ⋮ Dense trees: a new look at degenerate graphs ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ Differential geometric treewidth estimation in adiabatic quantum computation ⋮ Model counting for CNF formulas of bounded modular treewidth ⋮ Parameterized complexity of the \(k\)-arc Chinese postman problem ⋮ Characterizing width two for variants of treewidth ⋮ Exact algorithms and applications for tree-like Weighted Set Cover ⋮ Characterizations and algorithmic applications of chordal graph embeddings ⋮ Triangulating graphs without asteroidal triples ⋮ Matching interdiction ⋮ On interval routing schemes and treewidth ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ The density maximization problem in graphs ⋮ On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ On treewidth and minimum fill-in of asteroidal triple-free graphs ⋮ Improved Steiner tree algorithms for bounded treewidth ⋮ Bivariate complexity analysis of \textsc{Almost Forest Deletion} ⋮ On strongly \(\mathbb{Z}_{2s + 1}\)-connected graphs ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Weighted maximum-clique transversal sets of graphs ⋮ Refining the complexity of the sports elimination problem ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs ⋮ Approximation of minimum weight spanners for sparse graphs ⋮ Interval degree and bandwidth of a graph ⋮ Spanners of bounded degree graphs ⋮ Exact algorithms for edge domination ⋮ Computing bond orders in molecule graphs ⋮ Minesweeper on graphs ⋮ Splitting a graph into disjoint induced paths or cycles. ⋮ An FPT 2-approximation for tree-cut decomposition ⋮ Matchings with lower quotas: algorithms and complexity ⋮ Fast evaluation of interlace polynomials on graphs of bounded treewidth ⋮ Extended formulation for CSP that is compact for instances of bounded treewidth ⋮ Faster algorithms for finding and counting subgraphs ⋮ Decomposable convexities in graphs and hypergraphs ⋮ Acyclic and star colorings of cographs ⋮ The parameterized complexity of some minimum label problems ⋮ On the directed full degree spanning tree problem ⋮ On the vertex ranking problem for trapezoid, circular-arc and other graphs ⋮ A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ Clifford algebras meet tree decompositions ⋮ Approximation algorithms for digraph width parameters ⋮ On directed covering and domination problems ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ The complexity of minimum-length path decompositions ⋮ Explicit linear kernels for packing problems ⋮ Counting linear extensions: parameterizations by treewidth ⋮ The complexity of subgraph isomorphism for classes of partial k-trees ⋮ Crossing number for graphs with bounded pathwidth ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ On the parameterized complexity of the edge monitoring problem ⋮ Edge monitoring problem on interval graphs ⋮ Improved algorithms and complexity results for power domination in graphs ⋮ Network pollution games ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ Treewidth computations. I: Upper bounds ⋮ Separator orders in interval, cocomparability, and AT-free graphs ⋮ Towards fixed-parameter tractable algorithms for abstract argumentation ⋮ \(\mathcal Q\)-Ramsey classes of graphs ⋮ Minimum dominating set of queens: a trivial programming exercise? ⋮ Computing the branchwidth of interval graphs ⋮ Strong branchwidth and local transversals ⋮ Chordal deletion is fixed-parameter tractable ⋮ Complexity and approximation of the constrained forest problem ⋮ Domination in graphs with bounded propagation: Algorithms, formulations and hardness results ⋮ Understanding the scalability of Bayesian network inference using clique tree growth curves ⋮ Complexity of secure sets ⋮ Editing to a planar graph of given degrees ⋮ Parameterized complexity of length-bounded cuts and multicuts ⋮ The degree distribution of random \(k\)-trees ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ The parameterized complexity of the induced matching problem ⋮ Triangulating graphs with few \(P_4\)'s ⋮ Generating irregular partitionable data structures ⋮ Edge and node searching problems on trees ⋮ A survey on interval routing ⋮ Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth ⋮ The parameterised complexity of computing the maximum modularity of a graph ⋮ Parameterized leaf power recognition via embedding into graph products ⋮ Counting \(H-\)colorings of partial \(k-\)trees ⋮ An implementation of the iterative proportional fitting procedure by propagation trees. ⋮ Characterizing atoms that result from decomposition by clique separators ⋮ A new approach on locally checkable problems ⋮ Degree-constrained decompositions of graphs: Bounded treewidth and planarity ⋮ On the parameterized complexity of the expected coverage problem ⋮ Weighted proper orientations of trees and graphs of bounded treewidth ⋮ An analysis of the parameterized complexity of periodic timetabling ⋮ On structural parameterizations of the offensive alliance problem ⋮ Parameterized complexity of immunization in the threshold model ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ Vertex partitioning problems on graphs with bounded tree width ⋮ On some domination colorings of graphs ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Recent techniques and results on the Erdős-Pósa property ⋮ Complexity of edge monitoring on some graph classes ⋮ The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing ⋮ Sparse obstructions for minor-covering parameters ⋮ Hitting forbidden subgraphs in graphs of bounded treewidth ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ Parameterized algorithms for graph partitioning problems ⋮ Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees ⋮ New graph classes characterized by weak vertex separators and two-pairs ⋮ Space saving by dynamic algebraization based on tree-depth ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ Complexity and approximability of extended spanning star forest problems in general and complete graphs ⋮ Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Parameterized complexity of happy coloring problems ⋮ On the extremal sizes of maximal graphs without \(( k + 1 )\)-connected subgraphs ⋮ Contractible graphs for flow index less than three ⋮ Tractable cases of the extended global cardinality constraint ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Sketched representations and orthogonal planarity of bounded treewidth graphs ⋮ On caterpillar factors in graphs ⋮ On the tree-depth of random graphs ⋮ Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth ⋮ Counting solutions to CSP using generating polynomials ⋮ Parameterized algorithms for load coloring problem ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ Partition-based logical reasoning for first-order and propositional theories ⋮ Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes ⋮ The Small Set Vertex expansion problem ⋮ Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs ⋮ Node-searching problem on block graphs ⋮ Discrete optimization methods for group model selection in compressed sensing ⋮ Coloring temporal graphs ⋮ Tree decompositions of graphs: saving memory in dynamic programming ⋮ New width parameters for SAT and \#SAT ⋮ Detecting fixed patterns in chordal graphs in polynomial time ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem ⋮ On the complexity of connectivity in cognitive radio networks through spectrum assignment ⋮ An extended tree-width notion for directed graphs related to the computation of permanents ⋮ Kernels in planar digraphs ⋮ On some tractable and hard instances for partial incentives and target set selection ⋮ Algorithms for propositional model counting ⋮ Improved bottleneck domination algorithms ⋮ Complexity and algorithms for injective edge-coloring in graphs ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization ⋮ A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Hitting forbidden induced subgraphs on bounded treewidth graphs ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms ⋮ Using decomposition-parameters for QBF: mind the prefix! ⋮ Upper and lower degree-constrained graph orientation with minimum penalty ⋮ Structurally parameterized \(d\)-scattered set ⋮ 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 ⋮ Deleting vertices to graphs of bounded genus ⋮ The parameterized complexity of the minimum shared edges problem ⋮ Fast and parallel decomposition of constraint satisfaction problems ⋮ Defensive alliances in graphs ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ On the hardness of palletizing bins using FIFO queues ⋮ Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth ⋮ Mim-width. III. Graph powers and generalized distance domination problems ⋮ On the maximum weight minimal separator ⋮ On coloring a class of claw-free and hole-twin-free graphs ⋮ Measuring power in coalitional games with friends, enemies and allies ⋮ The complexity of finding harmless individuals in social networks ⋮ Separator-based graph embedding into multidimensional grids with small edge-congestion ⋮ Methods for solving reasoning problems in abstract argumentation -- a survey ⋮ Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization ⋮ Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions ⋮ Large hypertree width for sparse random hypergraphs ⋮ On the tree-depth and tree-width in heterogeneous random graphs ⋮ Capacitated domination: problem complexity and approximation algorithms ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree ⋮ On maximum independent set of categorical product and ultimate categorical ratios of graphs ⋮ Weighted modulo orientations of graphs and signed graphs ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results ⋮ A generic convolution algorithm for join operations on tree decompositions ⋮ Parameterized complexity of \((A,\ell)\)-path packing ⋮ On the parameterized complexity of the acyclic matching problem ⋮ Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree ⋮ Principled deep neural network training through linear programming ⋮ Exploiting Database Management Systems and Treewidth for Counting ⋮ Immunization in the threshold model: a parameterized complexity study ⋮ Linear‐time algorithms for eliminating claws in graphs ⋮ Minimum <scp>color‐degree</scp> perfect b‐matchings ⋮ Parameterized complexity of finding a spanning tree with minimum reload cost diameter ⋮ The k‐path vertex cover: General bounds and chordal graphs ⋮ Galactic token sliding ⋮ Parameterized intractability of defensive alliance problem ⋮ Approximating the bandwidth for asteroidal triple-free graphs ⋮ A parameterized approximation algorithm for the multiple allocation \(k\)-hub center ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Solving cut-problems in quadratic time for graphs with bounded treewidth ⋮ Algorithmic Aspects of Outer-Independent Total Roman Domination in Graphs ⋮ Weisfeiler-Leman indistinguishability of graphons ⋮ Fair division with minimal withheld information in social networks ⋮ On Interval Routing Schemes and treewidth ⋮ Arboreal Categories: An Axiomatic Theory of Resources ⋮ Linear Programs with Conjunctive Database Queries ⋮ On the parameterized complexity of s-club cluster deletion problems ⋮ On the parameterized complexity of \(s\)-club cluster deletion problems ⋮ Approximating sparse quadratic programs ⋮ Recognizing map graphs of bounded treewidth ⋮ Locating Eigenvalues of Symmetric Matrices - A Survey ⋮ Maximizing Social Welfare in Score-Based Social Distance Games ⋮ An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth ⋮ On the Parameterized Complexity of Clique Elimination Distance ⋮ Offensive alliances in graphs
