Cover Image

A Formal Correctness Proof of Edmonds' Blossom Shrinking Algorithm

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Abdulaziz, Mohammad, Mehlhorn, Kurt
Format:	Preprint
Published:	2024
Subjects:	Logic in Computer Science Data Structures and Algorithms 68, 90 F.4; F.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Formal Analysis of Algorithms for Matroids and Greedoids
by: Abdulaziz, Mohammad, et al.
Published: (2025)

Fair Vertex Problems Parameterized by Cluster Vertex Deletion
by: Masařík, Tomáš, et al.
Published: (2025)

A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Formalizing the notions of non-interactive and interactive algorithms
by: Middelburg, C. A.
Published: (2024)

Group Order Logic
by: Dahan, Anatole
Published: (2025)

A Counterexample to EFX $n \ge 3$ Agents, $m \ge n + 5$ Items, Submodular Valuations via SAT-Solving
by: Akrami, Hannaneh, et al.
Published: (2026)

Weakly acyclic diagrams: A data structure for infinite-state symbolic verification
by: Blondin, Michael, et al.
Published: (2024)

Formal Primal-Dual Algorithm Analysis
by: Abdulaziz, Mohammad, et al.
Published: (2026)

On the Length of Strongly Monotone Descending Chains over $\mathbb{N}^d$
by: Schmitz, Sylvain, et al.
Published: (2023)

Scalable Learning of One-Counter Automata via State-Merging Algorithms
by: Guha, Shibashis, et al.
Published: (2025)

On the formalization of the notion of an algorithm
by: Middelburg, C. A.
Published: (2024)

Subsequence Matching and Analysis Problems for Formal Languages
by: Fazekas, Szilárd Zsolt, et al.
Published: (2024)

On the formalization of the notion of a concurrent algorithm
by: Middelburg, C. A.
Published: (2024)

The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs
by: Chauhan, Archit, et al.
Published: (2024)

Set Parameterized Matching via Multi-Layer Hashing
by: Lewenstein, Moshe, et al.
Published: (2026)

A Polynomial-Time Deterministic Algorithm for an NP-Complete Problem
by: Jiang, Xinwen, et al.
Published: (2021)

Fast FPT Algorithms for Grundy Number on Dense Graphs
by: Nezhad, Sina Ghasemi, et al.
Published: (2024)

25 Additional Problems -- Extension to the Book "125 Problems in Text Algorithms"
by: Crochemore, Maxime, et al.
Published: (2025)

A (Weakly) Polynomial Algorithm for AIVF Coding
by: Dolatabadi, Reza Hosseini, et al.
Published: (2024)

Rabin Games and Colourful Universal Trees
by: Majumdar, Rupak, et al.
Published: (2024)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
by: Grochow, Joshua A., et al.
Published: (2021)

Count-Free Weisfeiler--Leman and Group Isomorphism
by: Collins, Nathaniel A., et al.
Published: (2022)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)

Deterministically Simulating Barely Random Algorithms in the Random-Order Arrival Model
by: Borodin, Allan, et al.
Published: (2025)

Strongly Sublinear Algorithms for Testing Pattern Freeness
by: Newman, Ilan, et al.
Published: (2021)

A note on the parameter $\ell$ in Buchbinder--Feldman's deterministic submodular matroid algorithm
by: Li, Shisheng
Published: (2026)

Minimizing Completion Times of Stochastic Jobs on Parallel Machines is Hard
by: Moseley, Benjamin, et al.
Published: (2026)

Matrix-by-matrix multiplication algorithm with $O(N^2log_2N)$ computational complexity for variable precision arithmetic
by: Paszyński, Maciej
Published: (2024)

Convergence analysis of t-SNE as a gradient flow for point cloud on a manifold
by: Jeong, Seonghyeon, et al.
Published: (2024)

An Efficient Algorithm for Unbalanced 1D Transportation
by: Gouvine, Gabriel
Published: (2023)

Better Algorithms for Constructing Minimum Cost Markov Chains and AIFV Codes
by: Dolatabadi, Reza Hosseini, et al.
Published: (2024)

Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
by: Bojikian, Narek, et al.
Published: (2025)

Strengths and Limitations of Greedy in Cup Games
by: Jasińska, Kalina, et al.
Published: (2026)

TreeWidzard: An Engine for Width-Based Dynamic Programming and Automated Theorem Proving
by: Oliveria, Mateus de Oliveira, et al.
Published: (2026)

Quantum Speedup for Some Geometric 3SUM-Hard Problems and Beyond
by: Keil, J. Mark, et al.
Published: (2024)

String 2-Covers with No Length Restrictions
by: Boneh, Itai, et al.
Published: (2024)

Minimum-cost paths for electric cars
by: Dorfman, Dani, et al.
Published: (2024)

Hairpin Completion Distance Lower Bound
by: Boneh, Itai, et al.
Published: (2024)

Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint
by: Filmus, Yuval, et al.
Published: (2024)

Overlapping Biclustering
by: Bentert, Matthias, et al.
Published: (2025)