Pith. sign in

REVIEW 1 cited by

Solving the Maximum-Weight Connected Subgraph Problem to Optimality

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1409.5308 v2 pith:ACQZM4DR submitted 2014-09-18 cs.DS

Mohammed El-Kebir , Gunnar W. Klau This is my paper · ORCID
classification cs.DS
keywords mwcsproblemconnectedsubgraphinstancesmaximum-weightoptimalitysolving
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

Given an undirected node-weighted graph, the Maximum-Weight Connected Subgraph problem (MWCS) is to identify a subset of nodes of maximalsum of weights that induce a connected subgraph. MWCS is closely related to the well-studied Prize Collecting Steiner Tree problem and has many applications in different areas, including computational biology, network design and computer vision. The problem is NP-hard and even hard to approximate within a constant factor. In this work we describe an algorithmic scheme for solving MWCS to provable optimality, which is based on preprocessing rules, new results on decomposing an instance into its biconnected and triconnected components and a branch-and-cut approach combined with a primal heuristic. We demonstrate the performance of our method on the benchmark instances of the 11th DIMACS implementation challenge consisting of MWCS as well as transformed PCST instances.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Open-World Video Segmentation

    cs.CV 2026-06 unverdicted novelty 7.0 of 10

    Savvy is a practical system for zero-shot open-world long-horizon video segmentation paired with the OGA granularity-aware evaluation protocol that uses n:1 matching and sever-point detection.

Pith tools