Efficient Reassembling of Three-Regular Planar Graphs


Assaf Kfoury∗
Boston University
Boston, Massachusetts
kfoury at bu dot edu
Ben Sisson∗
Boston University
Boston, Massachusetts
bmsisson at bu dot edu
The Alpha-Optimal Graph Reassembling Problem is closely related to, but different from, the Minimum Carving-Width Problem. The latter was defined in the following:
Seymour, P. D., and R. Thomas. “Call Routing and the Ratcatcher.” Combinatorica, vol. 14, no. 2, 1994, pp.
Our paper, Efficient Reassembling of Three-Regular Planar Graphs is based on results about the Alpha-Optimal Graph Reassembling Problem in two prior papers:
Assaf Kfoury and Saber Mirzaei. Efficient Reassembling of Graphs, Part 1: The Linear Case. Journal of Combinatorial Optimization, 33(3):1057–1089, April 2017
With later work on the problem in:
Saber Mirzaei and Assaf Kfoury. Efficient Reassembling of Graphs, Part 2: The Balanced Case. CoRR, abs/1602.02863, 2016. preprint, http://arxiv.org/abs/1602.02863v1
∗Partially supported by NSF awards CCF-0820138 and CNS-1135722.

Maintained by Ben Sisson (last updated 9/12/2018)
Created on 4/15/2018