Complexity framework for forbidden subgraphs. I: The framework
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 3848625 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 468640 (Why is no real title available?)
- scientific article; zbMATH DE number 1979486 (Why is no real title available?)
- scientific article; zbMATH DE number 3445275 (Why is no real title available?)
- scientific article; zbMATH DE number 969067 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- scientific article; zbMATH DE number 3043302 (Why is no real title available?)
- scientific article; zbMATH DE number 7651161 (Why is no real title available?)
- (Meta) kernelization
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A bound on the pathwidth of sparse graphs with applications to exact algorithms
- A dichotomy theorem for nonuniform CSPs
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A proof of the CSP dichotomy conjecture
- Algorithmic meta-theorems
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Boundary classes for graph problems involving non-local properties
- Boundary properties of graphs for algorithmic graph problems
- Coloring graphs characterized by a forbidden subgraph
- Coloring with no 2-colored \(P_4\)'s
- Complexity and algorithms for injective edge-coloring in graphs
- Complexity framework for forbidden subgraphs III: when problems are tractable on subcubic graphs
- Complexity framework for forbidden subgraphs. IV: The Steiner forest problem
- Complexity of \(C_k\)-coloring in hereditary classes of graphs
- Computational Complexity
- Contracting to a longest path in H-free graphs
- Cutting Barnette graphs perfectly is hard
- Easy problems for tree-decomposable graphs
- Edge Dominating Sets in Graphs
- Edge multiway cut and node multiway cut are hard for planar subcubic graphs
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Excluded grid minors and efficient polynomial-time approximation schemes
- FPT algorithms for domination in sparse graphs and beyond
- Face covers and the genus problem for apex graphs
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Generalized coloring for tree-like graphs
- Graph minors. III. Planar tree-width
- Graph minors. V. Excluding a planar graph
- Graph minors. XX: Wagner's conjecture
- Grid induced minor theorem for graphs of small degree
- Hard problems that quickly become very easy
- In absence of long chordless cycles, large tree-width becomes a local phenomenon
- Induced subgraphs and path decompositions
- Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
- Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- List coloring in the absence of two subgraphs
- Matching cuts in graphs of high girth and \(H\)-free graphs
- Mim-width. I. Induced path problems
- Min Cut is NP-complete for edge weighted trees
- Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
- Multi-multiway cut problem on graphs of bounded branch width
- NP-hard graph problems and boundary classes of graphs
- Node-and edge-deletion NP-complete problems
- On Linear Time Minor Tests with Depth-First Search
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- On maximum \(P_3\)-packing in claw-free subcubic graphs
- On nowhere dense graphs
- On some fine-grained questions in algorithms and complexity
- On the complexity of H-colouring planar graphs
- On the complexity of the disjoint paths problem
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- Planar graph bipartization in linear time
- Polynomial-time Algorithm for Maximum Weight Independent Set on P 6 -free Graphs
- Quickly excluding a forest
- Recognizing decomposable graphs
- Sparsity. Graphs, structures, and algorithms
- Steiner trees for hereditary graph classes: a treewidth perspective
- Structure theorem and isomorphism test for graphs with excluded topological subgraphs
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- Subgraph isomorphism on graph classes that exclude a substructure
- The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
- The Complexity of Multiterminal Cuts
- The Monotone Satisfiability Problem with Bounded Variable Appearances
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The Rectilinear Steiner Tree Problem is NP-Complete
- The complexity of \(H\)-colouring of bounded degree graphs
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The complexity of the matching-cut problem for planar graphs and other graph classes
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The perfect matching cut problem revisited
- The vertex separation and search number of a graph
- The vertex separation number of a graph equals its path-width
- Tree clustering for constraint networks
- Tree-width dichotomy
- Treewidth is NP-complete on cubic graphs
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- Unit disk graphs
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- \textsc{max-cut} and containment relations in graphs
This page was built for publication: Complexity framework for forbidden subgraphs. I: The framework
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7022268)
