Almost tight lower bounds for hard cutting problems in embedded graphs
From MaRDI portal
Recommendations
Cites work
- A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
- A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
- A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
- A separator theorem for graphs of bounded genus
- A tight lower bound for planar multiway cut with fixed number of terminals
- Can you beat treewidth?
- Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
- Genus characterizes the complexity of certain graph problems: Some tight results
- scientific article; zbMATH DE number 3314878 (Why is no real title available?)
- Lower bounds based on the exponential time hypothesis
- Optimally cutting a surface into a disk
- Parameterized algorithms
- Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- Subexponential parameterized odd cycle transversal on planar graphs
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The Complexity of Multiterminal Cuts
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
- When is the evaluation of conjunctive queries tractable?
- Which problems have strongly exponential complexity?
This page was built for publication: Almost tight lower bounds for hard cutting problems in embedded graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5088957)
