Cover Image

Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gawrychowski, Paweł, Wasylkiewicz, Mateusz
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Clique-free t-matchings in degree-bounded graphs
by: Paluch, Katarzyna, et al.
Published: (2024)

On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
by: Ghanbari, Babak, et al.
Published: (2025)

Triangle-free 2-matchings
by: Paluch, Katarzyna
Published: (2023)

Complexity of polytope diameters via perfect matchings
by: Nöbel, Christian, et al.
Published: (2024)

Reconfiguration of labeled matchings in triangular grid graphs
by: Kakimura, Naonori, et al.
Published: (2024)

Markovian protocols and an upper bound on the extension complexity of the matching polytope
by: Szusterman, M.
Published: (2026)

How to Reduce Temporal Cliques to Find Sparse Spanners
by: Angrick, Sebastian, et al.
Published: (2024)

On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2023)

Max Weight Independent Set in sparse graphs with no long claws
by: Abrishami, Tara, et al.
Published: (2023)

An algorithm with a delay of $\mathcal{O}(kΔ)$ for enumerating connected induced subgraphs of size $k$
by: Xiao, Chenglong, et al.
Published: (2024)

Deterministic approximation for the volume of the truncated fractional matching polytope
by: Guo, Heng, et al.
Published: (2024)

Designing sparse temporal graphs satisfying connectivity requirements
by: Bellitto, Thomas, et al.
Published: (2026)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
by: Shakeri, Heman, et al.
Published: (2025)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
by: Ghanbari, Babak, et al.
Published: (2026)

Path Contraction Faster than $2^n$
by: Agrawal, Akanksha, et al.
Published: (2025)

On the Structural Parameterizations of 2-Club with Triangle Constraints
by: Jacob, Ashwin, et al.
Published: (2025)

Approximating Maximum Edge 2-Coloring by Normalizing Graphs
by: Mömke, Tobias, et al.
Published: (2024)

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
by: Majewski, Konrad, et al.
Published: (2022)

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
by: Byrka, Jarosław, et al.
Published: (2024)

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
by: Dutta, Kunal, et al.
Published: (2026)

Maximum Biclique for Star 1,2,3 -free and Bounded Bimodularwidth Twin-free Bipartite Graphs $\star$
by: de Montgolfier, Fabien, et al.
Published: (2025)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
by: Korhonen, Tuukka, et al.
Published: (2024)

Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Finding Minimum Distance Preservers: A Parameterized Study
by: Simonov, Kirill, et al.
Published: (2026)

Boltzmann Sampling for Powersets without an Oracle
by: Peyen, Jean
Published: (2026)

The complexity of strong conflict-free vertex-connection $k$-colorability
by: Hsieh, Sun-Yuan, et al.
Published: (2024)

Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice
by: Tan, Jingjing
Published: (2024)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
by: Harada, Tsubasa
Published: (2024)

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Generation of weighted trees, block trees and block graphs
by: Ekim, Tınaz, et al.
Published: (2024)

Circular-arc graphs and the Helly property
by: Derbisz, Jan, et al.
Published: (2024)

Parameterized Saga of First-Fit and Last-Fit Coloring
by: Agrawal, Akanksha, et al.
Published: (2024)

Detecting Disjoint Shortest Paths in Linear Time and More
by: Akmal, Shyan, et al.
Published: (2024)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
by: Wang, Chen, et al.
Published: (2024)

A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
by: Harada, Tsubasa, et al.
Published: (2024)

Deterministic counting from coupling independence
by: Chen, Xiaoyu, et al.
Published: (2024)

Stability in Graphs with Matroid Constraints
by: Fomin, Fedor V., et al.
Published: (2024)

Generalizing Roberts' characterization of unit interval graphs
by: Martínez, Virginia Ardévol, et al.
Published: (2024)

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
by: Kaul, Matthias, et al.
Published: (2024)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
by: Disser, Yann, et al.
Published: (2024)