A single-exponential time 2-approximation algorithm for treewidth
From MaRDI portal
Cited in
(45)- When can cluster deletion with bounded weights be solved efficiently?
- On the parameterized complexity of computing good edge-labelings
- On the structural parameterized complexity of defective coloring
- A tight subexponential-time algorithm for two-page book embedding
- Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover
- A new width parameter of graphs based on edge cuts: -edge-crossing width
- A parameterized perspective of \textsc{all-colors}
- Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius
- The simultaneous interval number: a new width parameter that measures the similarity to interval graphs
- A parameterized perspective of \textsc{All-Colors}
- Computing twin-width parameterized by the feedback edge number
- Computing twin-width parameterized by the feedback edge number and vertex integrity
- A complexity-theoretic analysis of majority illusion in social networks
- On the parameterized complexity of Eulerian strong component arc deletion
- Parameterized complexity of weighted target set selection
- Shortest beer path queries in digraphs with bounded treewidth
- Computing paths of large rank in planar frameworks deterministically
- FPT approximation using treewidth: capacitated vertex cover, target set selection and vector dominating set
- On the parameterized complexity of computing tree-partitions
- Packing sets of paths, stars and triangles: tractability and approximability
- Polynomial-time algorithms for \textsc{Path Cover} on trees and graphs of bounded treewidth
- Computing treedepth in polynomial space and linear FPT time
- Embedding phylogenetic trees in networks of low treewidth
- Semi-proper orientations of dense graphs
- On the parameterized complexity of computing tree-partitions
- Sparse induced subgraphs of large treewidth
- The parameterized complexity landscape of the unsplittable flow problem
- Approximation algorithms for treewidth, pathwidth, and treedepth -- a short survey
- Approximating sparsest cut in low-treewidth graphs via combinatorial diameter
- Compound logics for modification problems
- On the parameterized complexity of computing st-orientations with few transitive edges
- On approximability of propositional model counting
- Nearly-tight bounds for flow sparsifiers in quasi-bipartite graphs
- Tree decompositions meet induced matchings: beyond max weight independent set
- Exact and heuristic computation of the scanwidth of directed acyclic graphs
- Residue domination in bounded-treewidth graphs
- A parameterized complexity analysis of bounded height depth-first search trees
- Parameterized spanning tree congestion
- A minor-testing approach for coordinated motion planning with sliding robots
- Temporal dominating set and temporal vertex cover under the lens of degree restrictions
- Parameterized algorithms for coordinated motion planning: minimizing energy
- Bridging treewidth and clique-width via cograph-modular-treewidth
- Tight (double) exponential bounds for identification problems: locating-dominating set and test cover
- Parameterized algorithms for k-inversion
- The leafed induced subtree in chordal and bounded treewidth graphs
This page was built for publication: A single-exponential time 2-approximation algorithm for treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6943525)
