The complexity of contracting bipartite graphs into small cycles
From MaRDI portal
Publication:6039435
DOI10.1007/978-3-031-15914-5_26arXiv2206.07358OpenAlexW4312799909MaRDI QIDQ6039435
Prafullkumar Tale, Roohani Sharma, R. Krithika
Publication date: 5 May 2023
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2206.07358
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On graph contractions and induced minors
- Parameterizing cut sets in a graph by the number of their components
- Contraction theorems in Hamiltonian graph theory
- Hierarchy of surface models and irreducible triangulations.
- Graph minors. XIII: The disjoint paths problem
- Disconnected cuts in claw-free graphs
- Detecting fixed patterns in chordal graphs in polynomial time
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
- Contractions of Planar Graphs in Polynomial Time
- Contractibility and NP-completeness
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- Cyclicity of graphs
- Distance-Preserving Graph Contractions
- RESTRICTED MESH SIMPLIFICATION USING EDGE CONTRACTIONS
- The complexity of satisfiability problems
- Contracting bipartite graphs to paths and cycles
- Contracting chordal graphs and bipartite graphs to paths and trees
- Contracting to a longest path in H-free graphs
This page was built for publication: The complexity of contracting bipartite graphs into small cycles
