Treewidth. Computations and approximations
From MaRDI portal
Publication:1338451
DOI10.1007/BFB0045375zbMATH Open0825.68144OpenAlexW4213368513MaRDI QIDQ1338451FDOQ1338451
Authors: Ton Kloks 
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
Recommendations
Cited In (only showing first 100 items - show all)
- Parameterized complexity of conflict-free matchings and paths
- Crossing number for graphs with bounded pathwidth
- Mim-width. III. Graph powers and generalized distance domination problems
- On the tree-depth and tree-width in heterogeneous random graphs
- Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
- Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges
- Weighted modulo orientations of graphs and signed graphs
- Algorithmic Aspects of Outer-Independent Total Roman Domination in Graphs
- Randomized rumor spreading in poorly connected small-world networks
- On tradeoffs between width- and fill-like graph parameters
- A generic convolution algorithm for join operations on tree decompositions
- Colorings with few colors: counting, enumeration and combinatorial bounds
- On some tractable and hard instances for partial incentives and target set selection
- Discrete optimization methods for group model selection in compressed sensing
- New width parameters for SAT and \#SAT
- A new approach on locally checkable problems
- On the Parameterized Complexity of Clique Elimination Distance
- The small set vertex expansion problem
- Complexity and algorithms for injective edge-coloring in graphs
- On structural parameterizations of the edge disjoint paths problem
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
- Parameterized complexity of conflict-free set cover
- Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
- On the parameterized complexity of the acyclic matching problem
- Some properties of random Apollonian networks
- A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
- Parameterized complexity of immunization in the threshold model
- Coloring temporal graphs
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Hitting forbidden subgraphs in graphs of bounded treewidth
- Deleting vertices to graphs of bounded genus
- An improved fixed-parameter algorithm for one-page crossing minimization
- Bisection of bounded treewidth graphs by convolutions
- Counting solutions to CSP using generating polynomials
- On the treewidth of random geometric graphs and percolated grids
- Complexity of edge monitoring on some graph classes
- Sparse obstructions for minor-covering parameters
- Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
- On the maximum weight minimal separator
- Parameterized complexity of conflict-free matchings and paths
- Structurally parameterized \(d\)-scattered set
- Title not available (Why is that?)
- On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs
- On the complexity of finding large odd induced subgraphs and odd colorings
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- Default logic and bounded treewidth
- Parameterized complexity of happy coloring problems
- Sketched representations and orthogonal planarity of bounded treewidth graphs
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- On structural parameterizations of the offensive alliance problem
- Tractable answer-set programming with weight constraints: bounded treewidth is not enough
- On structural parameterizations of the bounded-degree vertex deletion problem
- Walking through waypoints
- Complexity and approximability of extended spanning star forest problems in general and complete graphs
- On coloring a class of claw-free and hole-twin-free graphs
- The k‐path vertex cover: General bounds and chordal graphs
- Title not available (Why is that?)
- A parameterized complexity view on collapsing \(k\)-cores
- A linear time algorithm to list the minimal separators of chordal graphs
- A parameterized complexity view on collapsing \(k\)-cores
- Title not available (Why is that?)
- A Retrospective on (Meta) Kernelization
- On the vertex ranking problem for trapezoid, circular-arc and other graphs
- Separator orders in interval, cocomparability, and AT-free graphs
- I/O-efficient algorithms for graphs of bounded treewidth
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- Orthogonal planarity testing of bounded treewidth graphs
- Parameterized Complexity of $$(A,\ell )$$-Path Packing
- Collective tree spanners in graphs with bounded parameters
- Dense trees: a new look at degenerate graphs
- On the parameterized complexity of the expected coverage problem
- Complexity and approximation of the constrained forest problem
- Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
- Algebras for tree decomposable graphs
- A parameterized approximation algorithm for the multiple allocation \(k\)-hub center
- A \(c^k n\) 5-approximation algorithm for treewidth
- The complexity of finding harmless individuals in social networks
- On structural parameterizations of the bounded-degree vertex deletion problem
- Measuring power in coalitional games with friends, enemies and allies
- Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees
- Parameterized algorithms for load coloring problem
- Computing the branchwidth of interval graphs
- Defensive alliances in graphs
- A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem
- Improved bottleneck domination algorithms
- Subexponential time algorithms for finding small tree and path decompositions
- Extended formulation for CSP that is compact for instances of bounded treewidth
- Refining the complexity of the sports elimination problem
- Parameterized complexity of finding a spanning tree with minimum reload cost diameter
- Solving cut-problems in quadratic time for graphs with bounded treewidth
- Independent sets in asteroidal triple-free graphs
- Approximation algorithms for digraph width parameters
- Approximation of minimum weight spanners for sparse graphs
- Parameterized complexity of \((A,\ell)\)-path packing
- Minesweeper on graphs
- Metric Dimension of Bounded Tree-length Graphs
- On the extremal sizes of maximal graphs without \(( k + 1 )\)-connected subgraphs
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- The degree distribution of random \(k\)-trees
- On the parameterized complexity of computing balanced partitions in graphs
This page was built for publication: Treewidth. Computations and approximations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1338451)
