Tight bounds for the performance of Longest In System on DAGs

DOI10.1016/J.JALGOR.2004.04.013zbMATH Open1105.68004OpenAlexW2042849760MaRDI QIDQ3022748

Adi Rosén, Micah Adler

Publication date: 30 June 2005

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2004.04.013

zbMATH Keywords

adversarial queueing theory

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Network protocols (68M12)

Recommendations

• Tight lower bounds for the longest common extension problem 👍 👎
• A linear-time parameterized algorithm for computing the width of a DAG 👍 👎
• Fast Lowest Common Ancestor Computations in Dags 👍 👎
• Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n ² barrier 👍 👎
• Tight Bounds for Graph Problems in Insertion Streams 👍 👎
• Efficient Algorithms for k-Disjoint Paths Problems on DAGs 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Tight bounds for the performance of Longest In System on DAGs

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