Finding maximum weight 2-packing sets on arbitrary graphs

DOI10.1002/NET.70028MaRDI QIDQ7267794zbMATH OpenFDO

Authors Jannick Borowitz, Ernestine Großmann, Christian Schulz

Publication date 16 June 2026

Published in Networks (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1002/NET.70028

zbMATH Keywords

algorithm engineeringdata reduction rulesmaximum weight 2-packing setmaximum weight distance-3 independent set

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites work

• A Best Possible Heuristic for the k-Center Problem
• A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
• A genetic algorithm for the maximum 2-packing set problem
• A hybrid iterated local search heuristic for the maximum weight independent set problem
• A self-stabilizing algorithm for a maximal 2-packing in a cactus graph under any scheduler
• A self-stabilizing algorithm to maximal 2-packing with improved complexity
• Algorithm to find a maximum 2-packing set in a cactus
• Approximation algorithms for NP-complete problems on planar graphs
• Benchmarking optimization software with performance profiles.
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Data reduction and exact algorithms for clique cover
• Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs
• Effective data reduction for the vertex clique cover problem
• Efficient transformation of distance-2 self-stabilizing algorithms
• Exactly solving the maximum weight independent set problem on large real-world graphs
• Finding near-optimal independent sets at scale
• Finding near-optimal weight independent sets at scale
• H-free graphs, independent sets, and subexponential-time algorithms
• scientific article; zbMATH DE number 1223713 (Why is no real title available?)
• scientific article; zbMATH DE number 2061538 (Why is no real title available?)
• scientific article; zbMATH DE number 2114409 (Why is no real title available?)
• Improved (In-)Approximability Bounds for d-Scattered Set
• Neighborhood-restricted \([\leq 2]\)-achromatic colorings
• On the power of simple reductions for the maximum independent set problem
• Parsimonious formulations for low-diameter clusters
• Roman domination in graphs.
• Solving the maximum clique and vertex coloring problems on very large sparse networks
• The packing number of the double vertex graph of the path graph
• The University of Florida sparse matrix collection

This page was built for publication: Finding maximum weight 2-packing sets on arbitrary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7267794)