Cover Image

Polyhedral approach to weighted connected matchings in general graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Samer, Phillippe, Moura, Phablo F. S.
Format:	Preprint
Published:	2023
Subjects:	Discrete Mathematics Data Structures and Algorithms Combinatorics 90C27, 90C57, 90C11, 68R10 G.2.2; G.1.6; G.4
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Approximation algorithms for the prize-collecting rural postman problem
by: Li, Hong, et al.
Published: (2026)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
by: Rockel-Wolff, Benjamin
Published: (2024)

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
by: Chimani, Markus, et al.
Published: (2021)

Computing distances is FPT on graph associahedra and W[2]-hard on hypergraphic polytopes
by: Cunha, Luís Felipe I., et al.
Published: (2025)

Modern column generation for estimating single- and multi-purchase ranked list choice models
by: Costa, Luciano, et al.
Published: (2026)

A unified worst case for classical simplex and policy iteration pivot rules
by: Disser, Yann, et al.
Published: (2023)

Simple Approximations for General Spanner Problems
by: Bökler, Fritz, et al.
Published: (2025)

Exact Minimum Weight Spanners via Column Generation
by: Bökler, Fritz, et al.
Published: (2024)

Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection
by: Coppé, Vianney, et al.
Published: (2022)

Cluster deletion and clique partitioning in graphs with bounded clique number
by: Galesi, Nicola, et al.
Published: (2025)

Graph burning: an overview of mathematical programs
by: Cajica-Maceda, Lourdes Beatriz, et al.
Published: (2025)

A Polyhedral Perspective on the Perfect Matching Lattice
by: Silina, Olha
Published: (2025)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
by: Heimann, Sophia, et al.
Published: (2024)

The Bottom-Left Algorithm for the Strip Packing Problem
by: Hougardy, Stefan, et al.
Published: (2024)

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
by: Laekhanukit, Bundit
Published: (2024)

The Subspace Flatness Conjecture and Faster Integer Programming
by: Reis, Victor, et al.
Published: (2023)

From approximate to exact integer programming
by: Dadush, Daniel, et al.
Published: (2022)

Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN
by: Ali, Alejandro Mata
Published: (2025)

An improved approximation algorithm for k-Median
by: Young, Neal E.
Published: (2025)

A reliability-aware randomized simheuristic for the stochastic team orienteering problem
by: Circelli, Michele
Published: (2026)

Balanced connected partitions of edge-weighted graphs: Hardness and solving methods
by: Davari, Morteza, et al.
Published: (2025)

Loop unrolling of UCA models: distance labeling
by: Soulignac, Francisco J, et al.
Published: (2022)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
by: Heimann, Sophia, et al.
Published: (2025)

Greedy and randomized heuristics for optimization of k-domination models in digraphs and road networks
by: Dijkstra, Lukas, et al.
Published: (2024)

Census Dual Graphs: Properties and Random Graph Models
by: Anderson, Sara, et al.
Published: (2026)

Quantitative Indicators for Strength of Inequalities with Respect to a Polyhedron, Part I: Theory
by: Warme, David M.
Published: (2024)

Quantitative Indicators for Strength of Inequalities with Respect to a Polyhedron, Part II: Applications and Computational Evidence
by: Warme, David M.
Published: (2024)

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

Exact Dynamic Programming for Solow--Polasky Diversity Subset Selection on Lines and Staircases
by: Emmerich, Michael T. M.
Published: (2026)

Extending Exact Integrality Gap Computations for the Metric TSP
by: Cook, William, et al.
Published: (2026)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
by: Heimann, Sophia, et al.
Published: (2026)

Solving the Graph Burning Problem for Large Graphs
by: Pereira, Felipe de Carvalho, et al.
Published: (2024)

Extended Dijkstra algorithm and Moore-Bellman-Ford algorithm
by: Cheng, Cong-Dian
Published: (2017)

The partial gossip problem revisited
by: Kokhas, Konstantin, et al.
Published: (2026)

Troika algorithm: approximate optimization for accurate clique partitioning and clustering of weighted networks
by: Aref, Samin, et al.
Published: (2025)

Benchmarking of algorithms for set partitions
by: Khinvasara, Arnav, et al.
Published: (2026)

On the Importance of Studying the Membership Problem for Pedigree Polytopes
by: Arthanari, Tiru
Published: (2025)

On the characterization of graphs with tree 3-spanners
by: Lin, Lan, et al.
Published: (2025)

Asymmetry in the Complexity of the Multi-Commodity Network Pricing Problem
by: Bui, Quang Minh, et al.
Published: (2022)

A counterexample to the conjecture on Biclique Partition number of Split Graphs and related problems
by: Babu, Anand, et al.
Published: (2026)