Contractibility and NP-completeness
From MaRDI portal
Recommendations
- The complexity of graph contractions.
- The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
- On contracting graphs to fixed pattern graphs
- The computational complexity of graph contractions II: Two tough polynomially solvable cases
- Edge contractions in subclasses of chordal graphs
Cited in
(54)- Partitioning graphs into connected parts
- The isomorphism problem for classes of graphs closed under contraction
- Generalized partitions of graphs
- Hereditarily hard \(H\)-colouring problems
- Modulo orientations and matchings in graphs
- Disconnected cuts in claw-free graphs
- Detecting fixed patterns in chordal graphs in polynomial time
- Detecting induced star-like minors in polynomial time
- On the parameterized complexity of grid contraction
- Increasing the minimum degree of a graph by contractions
- Edge contractions in subclasses of chordal graphs
- Path contraction faster than 2ⁿ
- Partitioning Graphs into Connected Parts
- On contracting graphs to fixed pattern graphs
- Square contractions of graphs
- The Shrinking Property for NP and coNP
- The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
- The computational complexity of graph contractions II: Two tough polynomially solvable cases
- Increasing the minimum degree of a graph by contractions
- Detecting induced minors in AT-free graphs
- On graph contractions and induced minors
- Edge contractions in subclasses of chordal graphs
- Theory-Contraction is NP-Complete
- Parameterized complexity of three edge contraction problems with degree constraints
- Disconnected cuts in claw-free graphs
- Improved kernel results for some FPT problems based on simple observations
- Path Contraction Faster Than 2^n
- scientific article; zbMATH DE number 2188410 (Why is no real title available?)
- A note on contracting claw-free graphs
- Contracting chordal graphs and bipartite graphs to paths and trees
- The complexity of graph contractions.
- Contracting bipartite graphs to paths and cycles
- Contracting bipartite graphs to paths and cycles
- Contracting chordal graphs and bipartite graphs to paths and trees
- The complexity of contracting bipartite graphs into small cycles
- Contracting to a longest path in H-free graphs
- Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
- On the Parameterized Complexity of Maximum Degree Contraction Problem.
- The shrinking property for NP and coNP
- Contracting planar graphs to contractions of triangulations
- Parameterizing cut sets in a graph by the number of their components
- An FPT-algorithm for recognizing k-apices of minor-closed graph classes
- Finding maximum common contractions between phylogenetic networks
- On the complexity of colouring by superdigraphs of bipartite graphs
- Revisiting path contraction and cycle contraction
- Parameterized complexity of biclique contraction and balanced biclique contraction
- Revisiting path contraction and cycle contraction
- Computing pivot-minors
- The complexity of contracting bipartite graphs into small cycles
- The parameterized landscape of labeled graph contractions
- Containment relations in split graphs
- Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs
- Edge-contraction problems
- On the parameterized complexity of maximum degree contraction problem
This page was built for publication: Contractibility and NP-completeness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3739139)
