Image de couverture de livre

The Complexity of Contracting Bipartite Graphs into Small Cycles

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Krithika, R., Sharma, Roohani, Tale, Prafullkumar
Format:	Preprint
Publié:	2022
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
par: Krithika, R., et autres
Publié: (2023)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
par: Tale, Prafullkumar
Publié: (2025)

Balanced Substructures in Bicolored Graphs
par: Ardra, P. S., et autres
Publié: (2024)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
par: Foucaud, Florent, et autres
Publié: (2023)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
par: Foucaud, Florent, et autres
Publié: (2024)

Revisiting Path Contraction and Cycle Contraction
par: Krithika, R., et autres
Publié: (2024)

The Parameterized Complexity of Computing the VC-Dimension
par: Foucaud, Florent, et autres
Publié: (2025)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
par: Chakraborty, Dipayan, et autres
Publié: (2024)

A Single Exponential-Time FPT Algorithm for Cactus Contraction
par: Krithika, R., et autres
Publié: (2025)

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
par: Gaikwad, Ajinkya, et autres
Publié: (2025)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
par: Greilhuber, Jakob, et autres
Publié: (2026)

A Finer View of the Parameterized Landscape of Labeled Graph Contractions
par: Mathur, Yashaswini, et autres
Publié: (2025)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
par: Gupta, Chetan, et autres
Publié: (2025)

On the Equivalence of Gaussian Graphical Models Defined on Complete Bipartite Graphs
par: Molkaraie, Mehdi
Publié: (2025)

Geometric Bipartite Matching is in NC
par: Bhore, Sujoy, et autres
Publié: (2024)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
par: Esmer, Barış Can, et autres
Publié: (2022)

Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter
par: Lucke, Felicia
Publié: (2025)

Monotone Contractions
par: Batziou, Eleni, et autres
Publié: (2024)

On the Complexity of Nucleolus Computation for Bipartite b-Matching Games
par: Koenemann, Jochen, et autres
Publié: (2021)

The Computational Complexity of Factored Graphs
par: Gupta, Shreya, et autres
Publié: (2024)

The Parameterized Landscape of Labeled Graph Contractions
par: Lafond, Manuel, et autres
Publié: (2025)

On the Complexity of Problems on Tree-structured Graphs
par: Bodlaender, Hans L., et autres
Publié: (2022)

The Parameterized Complexity of Coloring Mixed Graphs
par: Lauerbach, Antonio, et autres
Publié: (2026)

Hexasort -- The Complexity of Stacking Colors on Graphs
par: Klocker, Linus, et autres
Publié: (2026)

On the Complexity of Vertex-Splitting Into an Interval Graph
par: Abu-Khzam, Faisal N., et autres
Publié: (2026)

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
par: Kocurek, Nicholas, et autres
Publié: (2026)

Double Exponential Lower Bound for Telephone Broadcast
par: Tale, Prafullkumar
Publié: (2024)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
par: Lokshtanov, Daniel, et autres
Publié: (2024)

Bipartite Matching is in Catalytic Logspace
par: Agarwala, Aryan, et autres
Publié: (2025)

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
par: Liu, Brian, et autres
Publié: (2024)

On the Parameterized Complexity of Semitotal Domination on Graph Classes
par: Retschmeier, Lukas
Publié: (2025)

On the Structure of Hamiltonian Graphs with Small Independence Number
par: Jedličková, Nikola, et autres
Publié: (2024)

On the Complexity of Bipartite Degree Realizability
par: Miklós, István
Publié: (2025)

Linking Bipartiteness and Inversion in Algebra via Graph‐Theoretic Methods and Simulink
par: Mohammad Mazyad Hazzazi, et autres
Publié: (2025)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
par: Komarath, Balagopal, et autres
Publié: (2025)

A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
par: Janzer, Oliver, et autres
Publié: (2024)

Local Test for Unitarily Invariant Properties of Bipartite Quantum States
par: Chen, Kean, et autres
Publié: (2024)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
par: Hörsch, Florian, et autres
Publié: (2025)

One-way Communication Complexity of Minimum Vertex Cover in General Graphs
par: Derakhshan, Mahsa, et autres
Publié: (2025)

Disrupting Bipartite Trading Networks: Matching for Revenue Maximization
par: D'Amico-Wong, Luca, et autres
Publié: (2024)