On the complexity of compressing two dimensional routing tables with order

DOI10.1007/s00453-016-0243-7zbMath1386.68070OpenAlexW2555027730MaRDI QIDQ1702127

Joanna Moulierac, Frédéric Havet, Frederic 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 algorithmorderpriorityroutingsoftware defined networksrouting tablescompact tables

Mathematics Subject Classification ID

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

Related Items (1)

Faster compression of patterns to rectangle rule lists

Cites Work

• Compressing two-dimensional routing tables with order
• Feedback arc set in bipartite tournaments is NP-complete
• Compressing two-dimensional routing tables
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• Maximum-Minimum Sätze über Graphen
• Integral Boundary Points of Convex Polyhedra
• Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments
• On the approximability of the maximum common subgraph problem
• Unnamed Item
• Unnamed Item

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