scientific article; zbMATH DE number 6783432
From MaRDI portal
Publication:5365080
Recommendations
- Known algorithms on graphs of bounded treewidth are probably optimal
- A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
- Dynamic algorithms for graphs of bounded treewidth
- Dynamic algorithms for graphs of bounded treewidth
- Tree-Width and Optimization in Bounded Degree Graphs
- I/O-efficient algorithms for graphs of bounded treewidth
- I/O-efficient algorithms for graphs of bounded treewidth
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- scientific article; zbMATH DE number 4060712
Cited in
(58)- Complete-subgraph-transversal-sets problem on bounded treewidth graphs
- Fine-grained parameterized complexity analysis of graph coloring problems
- A generic convolution algorithm for join operations on tree decompositions
- New limits of treewidth-based tractability in optimization
- Lower bounds for protrusion replacement by counting equivalence classes
- On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon
- Width, depth, and space: tradeoffs between branching and dynamic programming
- Computing the chromatic number using graph decompositions via matrix rank
- Pure Nash equilibria in graphical games and treewidth
- Faster exponential-time algorithms in graphs of bounded average degree
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
- Hitting forbidden subgraphs in graphs of bounded treewidth
- Characterizing graphs of maximum matching width at most 2
- Maximum matching width: new characterizations and a fast algorithm for dominating set
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- On the hardness of losing width
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- On the optimality of pseudo-polynomial algorithms for integer programming
- On the hardness of losing width
- Fixed-parameter tractability of treewidth and pathwidth
- What's next? Future directions in parameterized complexity
- Can you beat treewidth?
- Data reduction for graph coloring problems
- Parameterized (approximate) defective coloring
- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- On the equivalence among problems of bounded width
- Tree-Width and Optimization in Bounded Degree Graphs
- Data reduction for graph coloring problems
- Courcelle's theorem -- a game-theoretic approach
- Known algorithms on graphs of bounded treewidth are probably optimal
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
- On algorithms employing treewidth for L-bounded cut problems
- Confronting intractability via parameters
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Finer tight bounds for coloring on clique-width
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- On the optimality of pseudo-polynomial algorithms for integer programming
- Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
- Fast Algorithms for Join Operations on Tree Decompositions
- On the Parameterized Complexity of [1,j]-Domination Problems
- Parameterized (approximate) defective coloring
- Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
- Parameterized orientable deletion
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- scientific article; zbMATH DE number 7278055 (Why is no real title available?)
- Fine-grained parameterized complexity analysis of graph coloring problems
- Scheduling partially ordered jobs faster than \(2^n\)
- Width-parametrized SAT: time-space tradeoffs
- Dynamic programming for graphs on surfaces
- The parameterized complexity of finding minimum bounded chains
- Edge bipartization faster than \(2^k\)
- A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
- Homology localization through the looking-glass of parameterized complexity theory
- Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis
- Extended formulation for CSP that is compact for instances of bounded treewidth
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5365080)
