Residual Neural Terminal Constraint for MPC-based Collision Avoidance in Dynamic Environments

Bojan Deraji\'c; Mohamed-Khalil Bouzidi; Sebastian Bernhard; Wolfgang H\"onig

REVIEW 3 major objections 3 minor 33 references

Residual Neural Terminal Constraint for MPC-based Collision Avoidance in Dynamic Environments

T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read By writing the Hamilton-Jacobi value function as the signed distance function minus a non-negative learned residual, this paper builds a real-time MPC terminal constraint whose safe set is never larger than the SDF's, and reports up to…

desk verdict Plausible safety-by-construction trick, but the record's full text is the wrong paper and the abstract omits the invariance condition needed for the closed-loop guarantee. read the letter →

arxiv 2508.03428 v2 pith:QE3F37AR submitted 2025-08-05 cs.RO cs.LGcs.SYeess.SY

Bojan Derajić , Mohamed-Khalil Bouzidi , Sebastian Bernhard , Wolfgang Hönig This is my paper · ORCID

classification cs.ROcs.LGcs.SYeess.SY

keywords ModelpredictivecontrolHamilton-JacobireachabilitySigneddistancefunctionNeuralresidualHypernetworkCollisionavoidanceDynamicenvironmentsTerminalconstraint

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper aims to make Hamilton-Jacobi reachability practical for real-time robot navigation. It claims that the HJ value function can be decomposed as the signed distance function (SDF) to nearby obstacles minus a non-negative residual, and that a neural network with non-negative outputs can learn that residual. Plugging the resulting estimate into an MPC terminal constraint yields a planner whose terminal safe set is contained in the SDF safe set, so it is "at least as safe as the SDF by design." In simulation and hardware experiments, the method is reported to achieve up to 30% higher success rates than three state-of-the-art baselines with similar computational effort and low travel time.

What carries the argument

The load-bearing object is the decomposition identity $V(x,t) = \mathrm{SDF}(x,t) - r(x,t)$ for the Hamilton-Jacobi reachability value function. The signed distance term is computed from local observations in real time; the unknown residual captures the extra shrinkage of the true safe set due to obstacle motion and dynamics, and is represented by a neural network constrained to non-negative outputs. A hypernetwork generates the residual network's weights from the current situation, and the terminal constraint $\hat{V}(x_N) \ge 0$ is enforced inside MPC. The argument's work is done by the inequality $\hat{V} \le V$ (via $r \ge 0$), which makes the learned terminal set a subset of the SDF safe set.

What would settle it

Run the trained residual estimator on obstacle trajectories and environment layouts drawn from a distribution distinct from the training set, and compare its zero-superlevel set against the true HJ reachable set computed by grid-based dynamic programming for a small state space; if the estimate ever includes states where the true value function is negative, or if closed-loop success rates fall back to the SDF baseline, the generalization premise fails.

Watch

Extended reading notes

Core claim

The central claim is that for local MPC in dynamic environments, the time-varying safe set can be represented as the zero-superlevel set of $\hat{V}(x,t) = \mathrm{SDF}(x,t) - r_\theta(x,t)$, where $r_\theta \geq 0$ is a neural residual parameterized by a hypernetwork. Because the residual is non-negative, $\hat{V} \le \mathrm{SDF}$ everywhere, so the set $\{\hat{V} \ge 0\}$ is contained in the SDF safe set; this containment is the design-level safety property. The paper argues that this estimate is accurate enough for real-time MPC terminal constraints and demonstrates improved success rates in dynamic obstacle avoidance compared to three baselines.

Load-bearing premise

The load-bearing premise is that the offline-trained residual and hypernetwork generalize to unseen deployment conditions; separately, the closed-loop safety claim assumes the terminal superlevel set is effectively invariant, a condition the paper's abstract does not state.

Editorial extensions

If this is right

The expensive Hamilton-Jacobi computation is replaced by an SDF query plus a network forward pass, so time-varying safe sets become usable as MPC terminal constraints in real time.
Because the non-negative residual keeps the estimated safe set inside the SDF safe set, every trajectory admitted by the terminal constraint is at least as conservative as a pure SDF trajectory, by design.
The reported up-to-30% success-rate improvement over three state-of-the-art baselines comes at similar computational effort and with low travel time.
The hypernetwork parameterization is intended to improve real-time performance and generalization of the residual across local obstacle configurations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same decomposition could be applied to other conservative surrogates of reachability, such as control barrier functions, turning any cheap lower bound into a learned tight estimate so long as the learned correction is kept one-sided.
A direct quantitative test the paper leaves implicit is comparing $\hat{V}$ against a brute-force HJ solution on small grid benchmarks to map how approximation error grows with obstacle speed, density, and horizon.
The safety argument is only as strong as the invariance of the synthesized terminal set; making the invariance condition explicit and verifiable would turn the design-level "at least as safe as SDF" statement into a closed-loop guarantee.
One could trade the non-negativity constraint for a signed residual in regimes where performance matters more than conservatism, at the cost of losing the guaranteed containment.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things you should know. First, the full text on this record is not this paper—it's an unrelated cs.DS manuscript about de Bruijn graphs. So everything below rests on the abstract alone. Second, the core idea is actually plausible: writing the HJ value function as SDF minus a non-negative learned residual gives you a set containment by construction, which is a genuinely neat way to get a conservative learned safe set. The hypernetwork parametrization for time-varying sets is a reasonable addition.

The paper does something worth credit: instead of learning the value function directly and hoping for safety, it factors out the signed distance function and forces the residual to be non-negative. That means the estimated zero-superlevel set is provably inside the SDF safe set, independent of training quality. That is a clean observation.

The soft spot is the jump from that static containment to a closed-loop guarantee. A terminal constraint in MPC preserves safety only if the terminal set is invariant under the controller, or at least if recursive feasibility holds. The abstract's phrase 'at least as safe as the SDF by design' is true of the set geometry but doesn't automatically transfer to trajectories. The authors don't state or prove an invariance condition. That's a load-bearing omission. A state can be inside the estimated set at the terminal step and still violate the SDF constraint one step later if the set isn't invariant. This isn't a minor nit; it's the difference between a safety guarantee and a heuristic.

Everything else is proportionate. The 30% success-rate improvement over three baselines is a number with no error bars, named baselines, or scenario detail in the abstract. The generalization of the offline-trained residual to deployment is also an open question. These are normal things to check in a full paper, not fatal flaws.

Who's the audience? People working on MPC with learned safety filters, especially drone and mobile-robot planners. If the full paper addresses recursive feasibility—even empirically with terminal-set tightening—this is a solid contribution worth a serious referee. As supplied, the record is unreviewable because of the wrong full text. I'd ask the authors for the correct version before sending it out.

Referee Report

3 major / 3 minor

Summary. The manuscript as submitted consists of an abstract for a robotics paper titled "Residual Neural Terminal Constraint for MPC-based Collision Avoidance in Dynamic Environments" (arXiv:2508.03428), followed by a full text that is a different paper, arXiv:2508.03433, "When is String Reconstruction using de Bruijn Graphs Hard?", by different authors and on a different subject. The abstract proposes a hybrid MPC local planner in which a time-varying safe set is represented as the zero-superlevel set of a Hamilton-Jacobi (HJ) reachability value function, approximated in real time by decomposing the value function into a signed distance function (SDF) minus a non-negative residual modeled by a neural network and parametrized by a hypernetwork; the residual is applied as an MPC terminal constraint and claimed to be "at least as safe as the SDF by design" and to achieve up to 30% higher success rates than three state-of-the-art baselines with similar computational effort and low travel time. The supplied full text contains no derivation of the SDF-minus-residual decomposition, no MPC formulation, no training procedure, no safety proof, and no simulation or hardware experiments.

Significance. If the abstract's claims are correct, the work would be a practically significant contribution to real-time safe navigation: the static containment argument from V_hat = SDF - r with r >= 0 to {V_hat >= 0} being a subset of the SDF safe set is simple and credible, and a 30% success-rate improvement over strong baselines at similar computational cost would be valuable. The proposed decomposition of the HJ value function as an SDF minus a non-negative residual, if rigorously established, would be an elegant bridge between reachability analysis and learning-based planning. However, the submitted manuscript provides no derivations, no machine-checked proofs, no reproducible code, and no experimental data; the full text is unrelated to the abstract, so none of the claimed contributions can be verified from the submitted record.

major comments (3)

[Full Text (arXiv:2508.03433)] The full text supplied is not the paper described in the abstract. It is a de Bruijn-graph string-reconstruction paper with a different title, a different author list, and a different subject matter; it contains no mention of MPC, Hamilton-Jacobi reachability, signed distance functions, residual networks, hypernetworks, collision avoidance, or the three baseline methods. Consequently, every load-bearing claim in the abstract — the SDF-minus-residual decomposition, the non-negative residual construction, the terminal-constraint safety guarantee, and the 30% success-rate improvement — is unsupported in the submitted record. This is not a local presentation issue; the central contribution cannot be assessed from the submitted manuscript.
[Abstract] The safety claim "at least as safe as the SDF by design" is a static containment claim: if V_hat = SDF - r with r >= 0, then the zero-superlevel set of V_hat is contained in the zero-superlevel set of the SDF. In an MPC terminal-constraint formulation, this containment is not by itself sufficient for closed-loop collision avoidance; the terminal set must be a controlled invariant set for the dynamics (or recursive feasibility must be established) so that a state satisfying V_hat(x_N) >= 0 at the terminal step leads to a trajectory that also satisfies the safety constraint in the next control interval. The abstract and the supplied full text state neither such an invariance condition nor a proof that the learned terminal set enjoys it, so the central safety guarantee is not established. A concrete test would be a theorem showing that, for the proposed policy, membership in {V_hat >= 0} implies that the subsequent closed-loop state remains in the safe set on the next horizon; if this holds only under additional assumptions on the residual or the dynamics, those assumptions must be stated and verified.
[Abstract] The empirical claim of up to 30% higher success rates compared to three state-of-the-art baselines cannot be checked: the submitted text does not identify the baselines, the simulation environments, the obstacle dynamics, the hardware platform, the training data, or the evaluation protocol. Moreover, the residual network and hypernetwork are trained offline and must generalize to unseen environments and hardware conditions; the abstract asserts "generalization properties" without providing any procedure or evidence. Without these details, the reported improvement is an unsupported assertion rather than a verified result.

minor comments (3)

[Abstract] The term "hybrid MPC" is used without definition; if the final paper retains this term, it should be defined at first use.
[Abstract] The three state-of-the-art baseline methods are not named; when the full paper is supplied, they should be identified so that the comparison can be evaluated.
[Title / Full Text] The submission metadata should be reconciled: the title and abstract refer to arXiv:2508.03428, while the full text is arXiv:2508.03433 with a different title and author list.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular step exhibited: the safety containment follows from the non-negative residual construction, and the invariance gap is a correctness issue, not a reduction of a prediction to its inputs.

full rationale

The abstract's central safety claim is not circular: it defines the estimate as V_hat = SDF - r_hat with r_hat >= 0, so {V_hat >= 0} is a subset of {SDF >= 0} follows from the sign constraint alone; no fitted parameter, self-citation, or hidden equation is needed to exhibit this reduction. The decomposition V = SDF - r is presented as a property of the HJ value function used to motivate the network parameterization, not as a prediction validated by the same data. The 30% success-rate comparison is an empirical claim, and while the supplied full text is arXiv:2508.03433 (a de Bruijn graph string-reconstruction paper) rather than the MPC paper arXiv:2508.03428, this mismatch makes the experiments unauditable but does not itself demonstrate that any result reduces to its inputs by construction. The abstract's silence on controlled invariance or recursive feasibility of the learned terminal set is a correctness gap: terminal-set containment alone does not imply closed-loop collision avoidance, but that is a missing hypothesis, not a circular step under the definitions of this review. No specific equation or citation chain can be quoted that makes a prediction equivalent to an input, so the honest finding is no significant circularity.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central claims rest on two fitted model families (the residual network and the hypernetwork), whose weights are learned offline and are not specified in the abstract. The by-construction safety property additionally depends on the standard reachability decomposition V = SDF - r with r >= 0, and on the design choice of a non-negative network output. The largest unstated burden is generalization: the trained components must transfer from their training scenarios to the deployment environments, obstacle dynamics, and hardware conditions used in the evaluation. The abstract reports no distribution-shift analysis, no error bars, and no separation of training versus evaluation scenarios.

free parameters (2)

residual neural network weights = not stated in abstract (offline training)
The residual r(x) = SDF(x) - V_HJ(x) is approximated by a neural network; the empirical success claims depend on how well these weights reproduce the true residual.
hypernetwork weights = not stated in abstract (offline training)
The hypernetwork maps local observations to the residual network parameters; its generalization determines the accuracy of the time-varying safe set in unseen environments.

assumptions (4)

domain assumption The HJ value function satisfies V = SDF - r with r >= 0 for the considered reachability problem.
Under the standard formulation where the running cost is the signed distance and the horizon includes t = 0, V(x) <= SDF(x) holds, so the residual is non-negative; the abstract asserts this decomposition as the paper's starting point.
domain assumption The zero-superlevel set of the SDF is a valid static safe set, and the value-function superlevel set is the correct time-varying safe terminal set.
The safety-by-design argument transfers the guarantee 'estimated set is a subset of the SDF set' into a collision-avoidance guarantee; this requires the SDF set to be the ground-truth safe geometry.
ad hoc to paper The learned residual and hypernetwork generalize from offline training scenarios to the runtime environments, obstacle configurations, and hardware conditions used in evaluation.
The claimed up to 30% success-rate advantage over baselines is an empirical property of the trained models, not of the architecture; no distribution-shift analysis or train/test separation is reported in the abstract.
ad hoc to paper The residual network output is constrained to be non-negative, so the estimate is a pointwise lower bound of the SDF.
This structural choice is the mechanism that makes 'at least as safe as the SDF by design' true; if the output layer allowed negative values, the containment claim would fail.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Residual Neural Terminal Constraint for MPC-based Collision Avoidance in Dynamic Environments." pith.science (2026). https://pith.science/paper/QE3F37AR

@misc{pith2026250803428,
  author       = {Pith},
  title        = {Pith review of: Residual Neural Terminal Constraint for MPC-based Collision Avoidance in Dynamic Environments},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QE3F37AR}},
  note         = {Machine review of arXiv:2508.03428}
}

read the original abstract

In this paper, we propose a hybrid MPC local planner that uses a learning-based approximation of a time-varying safe set, derived from local observations and applied as the MPC terminal constraint. This set can be represented as a zero-superlevel set of the value function computed via Hamilton-Jacobi (HJ) reachability analysis, which is infeasible in real-time. We exploit the property that the HJ value function can be expressed as a difference of the corresponding signed distance function (SDF) and a non-negative residual function. The residual component is modeled as a neural network with non-negative output and subtracted from the computed SDF, resulting in a real-time value function estimate that is at least as safe as the SDF by design. Additionally, we parametrize the neural residual by a hypernetwork to improve real-time performance and generalization properties. The proposed method is compared with three state-of-the-art methods in simulations and hardware experiments, achieving up to 30\% higher success rates compared to the best baseline while requiring a similar computational effort and producing high-quality (low travel-time) solutions.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 22 canonical work pages

[1]

Afanasev, Ren´ e van Bevern, and Oxana Yu

Vsevolod A. Afanasev, Ren´ e van Bevern, and Oxana Yu. Tsidulko. The hierarchical Chinese postman problem: The slightest disorder makes it hard, yet disconnectedness is manageable. Oper. Res. Lett., 49(2):270–277, 2021. URL: https://doi.org/10.1016/j.orl.2021.01.017, doi:10.1016/J.ORL. 2021.01.017

work page doi:10.1016/j.orl.2021.01.017 2021
[2]

Akrida, George B

Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Christoforos L. Raptopoulos. The temporal explorer who returns to the base. J. Comput. Syst. Sci. , 120:179–193, 2021. URL: https: //doi.org/10.1016/j.jcss.2021.04.001, doi:10.1016/J.JCSS.2021.04.001

doi:10.1016/j.jcss.2021.04.001 2021
[3]

On the complexity of positional sequenc- ing by hybridization

Amir Ben-Dor, Itsik Pe’er, Ron Shamir, and Roded Sharan. On the complexity of positional sequenc- ing by hybridization. J. Comput. Biol. , 8(4):361–371, 2002. doi:10.1089/106652701752236188

work page doi:10.1089/106652701752236188 2002
[4]

Giulia Bernardini, Huiping Chen, Gabriele Fici, Grigorios Loukides, and Solon P. Pissis. Reverse- safe data structures for text indexing. In Guy E. Blelloch and Irene Finocchi, editors, Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2020, Salt Lake City, UT, USA, January 5-6, 2020 , pages 199–213. SIAM, 2020. doi:10.1137/1.9...

work page doi:10.1137/1.9781611976007.16 2020
[5]

Giulia Bernardini, Huiping Chen, Gabriele Fici, Grigorios Loukides, and Solon P. Pissis. Reverse-safe text indexing. ACM J. Exp. Algorithmics , 26:1.10:1–1.10:26, 2021. doi:10.1145/3461698. 15

work page doi:10.1145/3461698 2021
[6]

Brightwell and Peter Winkler

Graham R. Brightwell and Peter Winkler. Counting Eulerian circuits is #P-complete. In Camil Demetrescu, Robert Sedgewick, and Roberto Tamassia, editors, Proceedings of the Seventh Work- shop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algo- rithmics and Combinatorics, ALENEX /ANALCO 2005, Vancouver, BC, Canada, 22 January ...

work page 2005
[7]

Edge exploration of temporal graphs

Benjamin Merlin Bumpus and Kitty Meeks. Edge exploration of temporal graphs. Algorith- mica, 85(3):688–716, 2023. URL: https://doi.org/10.1007/s00453-022-01018-7 , doi:10. 1007/S00453-022-01018-7

doi:10.1007/s00453-022-01018-7 2023
[8]

Massimo Cairo, Paul Medvedev, Nidia Obscura Acosta, Romeo Rizzi, and Alexandru I. Tomescu. Optimal omnitig listing for safe and complete contig assembly. In Juha K¨ arkk¨ ainen, Jakub Ra- doszewski, and Wojciech Rytter, editors, 28th Annual Symposium on Combinatorial Pattern Match- ing, CPM 2017, July 4-6, 2017, Warsaw, Poland , volume 78 of LIPIcs, pages...

doi:10.4230/lipics.cpm 2017

Show all 33 references

[9]

Tomescu, and Elia C

Massimo Cairo, Romeo Rizzi, Alexandru I. Tomescu, and Elia C. Zirondelli. Genome assembly, from practice to theory: Safe, complete and Linear-Time. ACM Trans. Algorithms, 20(1):4:1–4:26,
[10]

Pissis, and Giulia Punzi

Alessio Conte, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, and Giulia Punzi. Beyond the BEST theorem: Fast assessment of Eulerian trails. In Evripidis Bampis and Aris Pagourtzis, editors, Fundamentals of Computation Theory - 23rd International Symposium...

2021 doi
[11]

Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/ 978-3-319-21275-3

2015
[12]

Postman tour on a graph with precedence relation on arcs

Moshe Dror, Helman Stern, and Pierre Trudeau. Postman tour on a graph with precedence relation on arcs. Networks, 17(3):283–294, 1987. URL: https://doi.org/10.1002/net.3230170304, doi: 10.1002/NET.3230170304

1987 doi
[13]

On temporal graph exploration

Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. J. Comput. Syst. Sci. , 119:1–18, 2021. URL: https://doi.org/10.1016/j.jcss.2021.01.005, doi: 10.1016/J.JCSS.2021.01.005

2021 doi
[14]

Thomas Erlebach and Jakob T. Spooner. Faster exploration of degree-bounded temporal graphs. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK...

2018 doi
[15]

Thomas Erlebach and Jakob T. Spooner. Non-strict temporal exploration. In Andr´ ea Werneck Richa and Christian Scheideler, editors, Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29 - July 1, 2020, Pr...

2020 doi
[16]

An algorithm for the hierarchical Chinese postman prob- lem

Gianpaolo Ghiani and Gennaro Improta. An algorithm for the hierarchical Chinese postman prob- lem. Oper. Res. Lett., 26(1):27–32, 2000. doi:10.1016/S0167-6377(99)00046-2

doi
[17]

Lewis, Steven Skiena, and Pavel A

Sridhar Hannenhalli, William Feldman, Herbert F. Lewis, Steven Skiena, and Pavel A. Pevzner. Positional sequencing by hybridization. Comput. Appl. Biosci. , 12(1):19–24, 1996. URL: https: //doi.org/10.1093/bioinformatics/12.1.19, doi:10.1093/BIOINFORMATICS/12.1.19

1996 doi
[18]

¨Uber die m¨ oglichkeit, einen linienzug ohne wiederholung und ohne unterbrechung zu umfahren

Carl Hierholzer and Chr Wiener. ¨Uber die m¨ oglichkeit, einen linienzug ohne wiederholung und ohne unterbrechung zu umfahren. Mathematische Annalen, 6(1):30–32, 1873. 16
[19]

Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New Yo...

1972 doi
[20]

On the hierarchical Chinese Postman Problem with linear ordered classes

Peter Korteweg and Ton Volgenant. On the hierarchical Chinese Postman Problem with linear ordered classes. Eur. J. Oper. Res. , 169(1):41–52, 2006. URL: https://doi.org/10.1016/j. ejor.2004.06.003, doi:10.1016/J.EJOR.2004.06.003

2006 doi
[21]

Eulerian paths with regular constraints

Orna Kupferman and Gal Vardi. Eulerian paths with regular constraints. In Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier, editors, MFCS, volume 58 of LIPIcs, pages 62:1–62:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2016.doi:10.4230/LIPIcs.MFCS.2016.62

2016 doi
[22]

Toward perfect reads: self-correction of short reads via mapping on de Bruijn graphs

Antoine Limasset, Jean-Fran¸ cois Flot, and Pierre Peterlongo. Toward perfect reads: self-correction of short reads via mapping on de Bruijn graphs. Bioinform., 36(2):651, 2020. URL: https://doi. org/10.1093/bioinformatics/btz548, doi:10.1093/BIOINFORMATICS/BTZ548

2020 doi
[23]

Eulerian walks in temporal graphs

Andrea Marino and Ana Silva. Eulerian walks in temporal graphs. Algorithmica, 85(3):805–830, 2023. URL: https://doi.org/10.1007/s00453-022-01021-y , doi:10.1007/ S00453-022-01021-Y

2023 doi
[24]

Modeling biological problems in computer science: a case study in genome assembly

Paul Medvedev. Modeling biological problems in computer science: a case study in genome assembly. Briefings Bioinform. , 20(4):1376–1383, 2019. URL: https://doi.org/10.1093/bib/bby003, doi: 10.1093/BIB/BBY003

2019 doi
[25]

Spirakis

Othon Michail and Paul G. Spirakis. Traveling salesman problems in temporal graphs. Theor. Comput. Sci. , 634:1–23, 2016. URL: https://doi.org/10.1016/j.tcs.2016.04.006, doi:10. 1016/J.TCS.2016.04.006

2016 doi
[26]

Approximately counting approximately- shortest paths in directed acyclic graphs

Mat´ us Mihal´ ak, Rastislav Sr´ amek, and Peter Widmayer. Approximately counting approximately- shortest paths in directed acyclic graphs. Theory Comput. Syst. , 58(1):45–59, 2016. URL: https: //doi.org/10.1007/s00224-014-9571-7 , doi:10.1007/S00224-014-9571-7

2016 doi
[27]

Pevzner, Haixu Tang, and Michael S

Pavel A. Pevzner, Haixu Tang, and Michael S. Waterman. An Eulerian path approach to DNA fragment assembly. Proceedings of the National Academy of Sciences , 98(17):9748–9753,
[28]

Generalizing data to provide anonymity when disclosing information (abstract)

Pierangela Samarati and Latanya Sweeney. Generalizing data to provide anonymity when disclosing information (abstract). In Alberto O. Mendelzon and Jan Paredaens, editors, Proceedings of the Sev- enteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Ju...

1998
[29]

Graph transformation algorithm for the time dependent Chinese Postman Problem with Time Windows

Jinghao Sun, Guozhen Tan, and Xianchao Meng. Graph transformation algorithm for the time dependent Chinese Postman Problem with Time Windows. In 2011 International Conference on Mechatronic Science, Electric Engineering and Computer (MEC) , pages 955–960, 2011. doi:10. 1109/ME...

2011
[30]

k-Anonymity: A model for protecting privacy

Latanya Sweeney. k-Anonymity: A model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl. Based Syst. , 10(5):557–570, 2002. doi:10.1142/S0218488502001648

2002 doi
[31]

Tomescu and Paul Medvedev

Alexandru I. Tomescu and Paul Medvedev. Safe and complete contig assembly through omnitigs. J. Comput. Biol. , 24(6):590–602, 2017. URL: https://doi.org/10.1089/cmb.2016.0141, doi: 10.1089/CMB.2016.0141

2017
[32]

Time-constrained Chinese postman problems

Hsiao-Fan Wang and Yu-Pin Wen. Time-constrained Chinese postman problems. Computers & Mathematics with Applications , 44(3):375–387, 2002. URL: https://www.sciencedirect.com/ science/article/pii/S0898122102001566, doi:10.1016/S0898-1221(02)00156-6. 17 A Generalizations of the ...

2002 doi
[2001]

pnas.org/doi/pdf/10.1073/pnas.171285098, doi:10.1073/pnas.171285098

URL: https://www.pnas.org/doi/abs/10.1073/pnas.171285098, arXiv:https://www. pnas.org/doi/pdf/10.1073/pnas.171285098, doi:10.1073/pnas.171285098

doi

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Afanasev, Ren´ e van Bevern, and Oxana Yu

Vsevolod A. Afanasev, Ren´ e van Bevern, and Oxana Yu. Tsidulko. The hierarchical Chinese postman problem: The slightest disorder makes it hard, yet disconnectedness is manageable. Oper. Res. Lett., 49(2):270–277, 2021. URL: https://doi.org/10.1016/j.orl.2021.01.017, doi:10.1016/J.ORL. 2021.01.017

work page doi:10.1016/j.orl.2021.01.017 2021

[2] [2]

Akrida, George B

Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Christoforos L. Raptopoulos. The temporal explorer who returns to the base. J. Comput. Syst. Sci. , 120:179–193, 2021. URL: https: //doi.org/10.1016/j.jcss.2021.04.001, doi:10.1016/J.JCSS.2021.04.001

doi:10.1016/j.jcss.2021.04.001 2021

[3] [3]

On the complexity of positional sequenc- ing by hybridization

Amir Ben-Dor, Itsik Pe’er, Ron Shamir, and Roded Sharan. On the complexity of positional sequenc- ing by hybridization. J. Comput. Biol. , 8(4):361–371, 2002. doi:10.1089/106652701752236188

work page doi:10.1089/106652701752236188 2002

[4] [4]

Giulia Bernardini, Huiping Chen, Gabriele Fici, Grigorios Loukides, and Solon P. Pissis. Reverse- safe data structures for text indexing. In Guy E. Blelloch and Irene Finocchi, editors, Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2020, Salt Lake City, UT, USA, January 5-6, 2020 , pages 199–213. SIAM, 2020. doi:10.1137/1.9...

work page doi:10.1137/1.9781611976007.16 2020

[5] [5]

Giulia Bernardini, Huiping Chen, Gabriele Fici, Grigorios Loukides, and Solon P. Pissis. Reverse-safe text indexing. ACM J. Exp. Algorithmics , 26:1.10:1–1.10:26, 2021. doi:10.1145/3461698. 15

work page doi:10.1145/3461698 2021

[6] [6]

Brightwell and Peter Winkler

Graham R. Brightwell and Peter Winkler. Counting Eulerian circuits is #P-complete. In Camil Demetrescu, Robert Sedgewick, and Roberto Tamassia, editors, Proceedings of the Seventh Work- shop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algo- rithmics and Combinatorics, ALENEX /ANALCO 2005, Vancouver, BC, Canada, 22 January ...

work page 2005

[7] [7]

Edge exploration of temporal graphs

Benjamin Merlin Bumpus and Kitty Meeks. Edge exploration of temporal graphs. Algorith- mica, 85(3):688–716, 2023. URL: https://doi.org/10.1007/s00453-022-01018-7 , doi:10. 1007/S00453-022-01018-7

doi:10.1007/s00453-022-01018-7 2023

[8] [8]

Massimo Cairo, Paul Medvedev, Nidia Obscura Acosta, Romeo Rizzi, and Alexandru I. Tomescu. Optimal omnitig listing for safe and complete contig assembly. In Juha K¨ arkk¨ ainen, Jakub Ra- doszewski, and Wojciech Rytter, editors, 28th Annual Symposium on Combinatorial Pattern Match- ing, CPM 2017, July 4-6, 2017, Warsaw, Poland , volume 78 of LIPIcs, pages...

doi:10.4230/lipics.cpm 2017