Pith. sign in

REVIEW 1 cited by

A Dynamic Programming Framework for Combinatorial Optimization Problems on Graphs with Bounded Pathwidth

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 0806.0840 v2 pith:PZNLJ3RU submitted 2008-06-04 cs.DS cs.DM

Mugurel Ionut Andreica This is my paper · ORCID
classification cs.DScs.DM
keywords problemsgraphsboundedcombinatorialdynamicframeworknetworkoptimization
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

In this paper we present an algorithmic framework for solving a class of combinatorial optimization problems on graphs with bounded pathwidth. The problems are NP-hard in general, but solvable in linear time on this type of graphs. The problems are relevant for assessing network reliability and improving the network's performance and fault tolerance. The main technique considered in this paper is dynamic programming.

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. Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing

    cs.DS 2025-05 conditional novelty 7.0 of 10

    The paper proves that bounded bandwidth implies polylogarithmic BFS width, yielding first deterministic guarantees for Cuthill-McKee and near-linear graph reconstruction.

Pith tools