On the complexity of compressing two dimensional routing tables with order

DOI10.1007/S00453-016-0243-7MaRDI QIDQ1702127zbMATH OpenOpenAlexFDO

Authors Frédéric Havet, Joanna Moulierac, F. Giroire

Publication date 28 February 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01686641/file/compacting.pdf

zbMATH Keywords

complexityapproximation algorithmorderroutingprioritysoftware defined networksrouting tablescompact tables

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10)

Recommendations

• Compressing two-dimensional routing tables with order
• Compressing two-dimensional routing tables
• scientific article; zbMATH DE number 3940741
• The compactness of adaptive routing tables
• Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• Compressing two-dimensional routing tables
• Compressing two-dimensional routing tables with order
• Feedback arc set in bipartite tournaments is NP-complete
• Integral boundary points of convex polyhedra
• Internet packet filter management and rectangle geometry
• Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments
• Maximum-Minimum Sätze über Graphen
• On the approximability of the maximum common subgraph problem

Cited in

(3)

• Compressing two-dimensional routing tables with order
• Compressing two-dimensional routing tables
• Faster compression of patterns to rectangle rule lists

This page was built for publication: On the complexity of compressing two dimensional routing tables with order

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