{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T04:21:39Z","timestamp":1744258899048,"version":"3.40.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,25]],"date-time":"2025-01-25T00:00:00Z","timestamp":1737763200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,25]],"date-time":"2025-01-25T00:00:00Z","timestamp":1737763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Bergen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In this paper, we introduce a directed variant of the classical <jats:sc>Bandwidth<\/jats:sc>problem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of the directed variants of the classical <jats:sc>Cutwidth<\/jats:sc> and <jats:sc>Pathwidth<\/jats:sc> problems, we define <jats:sc>Digraph Bandwidth<\/jats:sc> as follows. Given a digraph <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{D}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>D<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> and an ordering <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{\\sigma }$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c3<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> of its vertices, the <jats:italic>digraph bandwidth<\/jats:italic> of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{\\sigma }$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c3<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> with respect to <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{D}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>D<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> is equal to the maximum value of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{\\sigma (v)}-\\varvec{\\sigma (u)}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>\u03c3<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>v<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mi>\u03c3<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>u<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> over all arcs <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{(u,v)}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>u<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>v<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{D}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>D<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> going forward along <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{\\sigma }$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c3<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> (that is, when <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{\\sigma (u)} &lt; \\varvec{\\sigma (v)}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>\u03c3<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>u<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mi>\u03c3<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>v<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>). The <jats:sc>Digraph Bandwidth<\/jats:sc> problem takes as input a digraph <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{D}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>D<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> and asks to output an ordering with the minimum digraph bandwidth. The undirected <jats:sc>Bandwidth<\/jats:sc>easily reduces to <jats:sc>Digraph Bandwidth<\/jats:sc> and thus, it immediately implies that <jats:sc>Digraph Bandwidth<\/jats:sc> is -hard. While an <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{\\mathcal {O}}^{\\star }\\varvec{(n!)}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mi>O<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mo>\u22c6<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>!<\/mml:mo>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> time algorithm for the problem is trivial, the goal of this paper is to design algorithms for <jats:sc>Digraph Bandwidth<\/jats:sc> which have running times of the form <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{2}^{\\varvec{\\mathcal {O}(n)}}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. In particular, we obtain the following results. Here, <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{n}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> and <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{m}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>m<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> denote the number of vertices and arcs of the input digraph <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varvec{D}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>D<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, respectively.<jats:list list-type=\"bullet\">\n              <jats:list-item>\n                <jats:p>\n                  <jats:sc>Digraph Bandwidth<\/jats:sc> can be solved in <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{\\mathcal {O}}^\\star (\\varvec{3}^{\\varvec{n}} \\cdot \\varvec{2}^{\\varvec{m}})$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:msup>\n                            <mml:mrow>\n                              <mml:mi>O<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>\u22c6<\/mml:mo>\n                          <\/mml:msup>\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mn>3<\/mml:mn>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mi>n<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>\u00b7<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mn>2<\/mml:mn>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mi>m<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula> time. This result implies a <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{2}^{\\varvec{\\mathcal {O}}(\\varvec{n})}$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:msup>\n                          <mml:mrow>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>O<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:msup>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula> time algorithm on sparse graphs, such as graphs of bounded average degree (planar graphs).<\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:p>Let <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{G}$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:mi>G<\/mml:mi>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula> be the underlying undirected graph of the input digraph. If the treewidth of <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{G}$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:mi>G<\/mml:mi>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula> is at most <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{t}$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:mi>t<\/mml:mi>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula>, then <jats:sc>Digraph Bandwidth<\/jats:sc> can be solved in time <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{\\mathcal {O}}^\\star (\\varvec{2}^{\\varvec{n} + (\\varvec{t}+\\varvec{2})\\, \\varvec{\\log }\\, \\varvec{n}})$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:msup>\n                            <mml:mrow>\n                              <mml:mi>O<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>\u22c6<\/mml:mo>\n                          <\/mml:msup>\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mn>2<\/mml:mn>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mrow>\n                                  <mml:mi>n<\/mml:mi>\n                                <\/mml:mrow>\n                                <mml:mo>+<\/mml:mo>\n                                <mml:mo>(<\/mml:mo>\n                                <mml:mrow>\n                                  <mml:mi>t<\/mml:mi>\n                                <\/mml:mrow>\n                                <mml:mo>+<\/mml:mo>\n                                <mml:mrow>\n                                  <mml:mn>2<\/mml:mn>\n                                <\/mml:mrow>\n                                <mml:mo>)<\/mml:mo>\n                                <mml:mspace\/>\n                                <mml:mrow>\n                                  <mml:mo>log<\/mml:mo>\n                                <\/mml:mrow>\n                                <mml:mspace\/>\n                                <mml:mrow>\n                                  <mml:mi>n<\/mml:mi>\n                                <\/mml:mrow>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula>. This result implies a <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{2}^{\\varvec{n}+\\varvec{\\mathcal {O}}(\\sqrt{\\varvec{n}}\\, \\varvec{\\log }\\, \\varvec{n})}$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:msup>\n                          <mml:mrow>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mi>O<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msqrt>\n                              <mml:mrow>\n                                <mml:mi>n<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msqrt>\n                            <mml:mspace\/>\n                            <mml:mrow>\n                              <mml:mo>log<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mspace\/>\n                            <mml:mrow>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:msup>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula> algorithm, for directed planar graphs and, in general, for the class of digraphs whose underlying undirected graph excludes some fixed graph <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{H}$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:mi>H<\/mml:mi>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula> as a minor.<\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:p>\n                  <jats:sc>Digraph Bandwidth<\/jats:sc> can be solved in <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{\\min } \\{ \\varvec{\\mathcal {O}}^{\\star }(\\varvec{4}^{\\varvec{n}} \\cdot \\varvec{b}^{\\varvec{n}}), \\varvec{\\mathcal {O}}^{\\star }(\\varvec{4}^{\\varvec{n}} \\cdot \\varvec{2}^{\\varvec{b}\\, \\varvec{\\log }\\, \\varvec{b}\\, \\varvec{\\log }\\, \\varvec{n}})\\}$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:mrow>\n                            <mml:mo>min<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:mo>{<\/mml:mo>\n                          <mml:msup>\n                            <mml:mrow>\n                              <mml:mi>O<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>\u22c6<\/mml:mo>\n                          <\/mml:msup>\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mn>4<\/mml:mn>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mi>n<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>\u00b7<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mi>b<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mi>n<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:mo>,<\/mml:mo>\n                          <mml:msup>\n                            <mml:mrow>\n                              <mml:mi>O<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>\u22c6<\/mml:mo>\n                          <\/mml:msup>\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mn>4<\/mml:mn>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mi>n<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>\u00b7<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mn>2<\/mml:mn>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mrow>\n                                  <mml:mi>b<\/mml:mi>\n                                <\/mml:mrow>\n                                <mml:mspace\/>\n                                <mml:mrow>\n                                  <mml:mo>log<\/mml:mo>\n                                <\/mml:mrow>\n                                <mml:mspace\/>\n                                <mml:mrow>\n                                  <mml:mi>b<\/mml:mi>\n                                <\/mml:mrow>\n                                <mml:mspace\/>\n                                <mml:mrow>\n                                  <mml:mo>log<\/mml:mo>\n                                <\/mml:mrow>\n                                <mml:mspace\/>\n                                <mml:mrow>\n                                  <mml:mi>n<\/mml:mi>\n                                <\/mml:mrow>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:mo>}<\/mml:mo>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula> time, where <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{b}$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:mi>b<\/mml:mi>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula> denotes the optimal digraph bandwidth of <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{D}$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:mi>D<\/mml:mi>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula>. This allow us to deduce a <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{2}^{\\varvec{\\mathcal {O}}(\\varvec{n})}$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:msup>\n                          <mml:mrow>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>O<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:msup>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula> algorithm in many cases, for example when <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{b} \\le \\frac{\\varvec{n}}{\\varvec{\\log }^{\\varvec{2}}\\,\\varvec{n}}$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:mrow>\n                            <mml:mi>b<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:mo>\u2264<\/mml:mo>\n                          <mml:mfrac>\n                            <mml:mrow>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:msup>\n                                <mml:mrow>\n                                  <mml:mo>log<\/mml:mo>\n                                <\/mml:mrow>\n                                <mml:mrow>\n                                  <mml:mn>2<\/mml:mn>\n                                <\/mml:mrow>\n                              <\/mml:msup>\n                              <mml:mspace\/>\n                              <mml:mrow>\n                                <mml:mi>n<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:mrow>\n                          <\/mml:mfrac>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula>.<\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:p>Finally, we give a <jats:italic>(Single) Exponential Time Approximation Scheme<\/jats:italic> for <jats:sc>Digraph Bandwidth<\/jats:sc>. In particular, we show that for any fixed real <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{\\epsilon } &gt; \\varvec{0}$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:mrow>\n                            <mml:mi>\u03f5<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:mo>&gt;<\/mml:mo>\n                          <mml:mrow>\n                            <mml:mn>0<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula>, we can find an ordering whose digraph bandwidth is at most <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$(\\varvec{1}+\\varvec{\\epsilon })$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:mo>(<\/mml:mo>\n                          <mml:mrow>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:mo>+<\/mml:mo>\n                          <mml:mrow>\n                            <mml:mi>\u03f5<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:mo>)<\/mml:mo>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula> times the optimal digraph bandwidth, in time <jats:inline-formula>\n                    <jats:alternatives>\n                      <jats:tex-math>$$\\varvec{\\mathcal {O}}^{{\\star }}(\\varvec{4}^{\\varvec{n}} \\cdot (\\lceil \\varvec{4}\/{\\varvec{\\epsilon }} \\rceil )^n)$$<\/jats:tex-math>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:msup>\n                            <mml:mrow>\n                              <mml:mi>O<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>\u22c6<\/mml:mo>\n                          <\/mml:msup>\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mn>4<\/mml:mn>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mi>n<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>\u00b7<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mo>(<\/mml:mo>\n                                <mml:mrow>\n                                  <mml:mo>\u2308<\/mml:mo>\n                                  <mml:mrow>\n                                    <mml:mn>4<\/mml:mn>\n                                  <\/mml:mrow>\n                                  <mml:mo>\/<\/mml:mo>\n                                  <mml:mrow>\n                                    <mml:mi>\u03f5<\/mml:mi>\n                                  <\/mml:mrow>\n                                  <mml:mo>\u2309<\/mml:mo>\n                                <\/mml:mrow>\n                                <mml:mo>)<\/mml:mo>\n                              <\/mml:mrow>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:alternatives>\n                  <\/jats:inline-formula>.<\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n          <\/jats:p>","DOI":"10.1007\/s00224-024-10202-x","type":"journal-article","created":{"date-parts":[[2025,1,25]],"date-time":"2025-01-25T10:13:28Z","timestamp":1737800008000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Exact and Approximate Digraph Bandwidth"],"prefix":"10.1007","volume":"69","author":[{"given":"Pallavi","family":"Jain","sequence":"first","affiliation":[]},{"given":"Lawqueen","family":"Kanesh","sequence":"additional","affiliation":[]},{"given":"Willian","family":"Lochet","sequence":"additional","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]},{"given":"Roohani","family":"Sharma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,25]]},"reference":[{"issue":"2","key":"10202_CR1","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1002\/(SICI)1097-0118(199906)31:2<75::AID-JGT1>3.0.CO;2-S","volume":"31","author":"Y Lai","year":"1999","unstructured":"Lai, Y., Williams, K.: A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs. J. Graph Theory 31(2), 75\u201394 (1999)","journal-title":"J. Graph Theory"},{"issue":"1","key":"10202_CR2","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.jctb.2011.05.001","volume":"102","author":"M Chudnovsky","year":"2012","unstructured":"Chudnovsky, M., Fradkin, A., Seymour, P.: Tournament immersion and cutwidth. J. Comb. Theory Ser. B 102(1), 93\u2013101 (2012)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"10202_CR3","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"M Garey","year":"1978","unstructured":"Garey, M., Graham, R., Johnson, D., Knuth, D.: Complexity results for bandwidth minimization. SIAM J. Appl. Math. 34(3), 477\u2013495 (1978)","journal-title":"SIAM J. Appl. Math."},{"key":"10202_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H (1979)"},{"issue":"3","key":"10202_CR5","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02280884","volume":"16","author":"CH Papadimitriou","year":"1976","unstructured":"Papadimitriou, C.H.: The NP-completeness of the bandwidth minimization problem. Computing 16(3), 263\u2013270 (1976)","journal-title":"Computing"},{"issue":"4","key":"10202_CR6","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0607057","volume":"7","author":"B Monien","year":"1986","unstructured":"Monien, B.: The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Alg. Discrete Meth. 7(4), 505\u2013512 (1986)","journal-title":"SIAM J. Alg. Discrete Meth."},{"key":"10202_CR7","unstructured":"Blache, G., Karpinski, M., Wirtgen, J.: On approximation intractability of the bandwidth problem. Electron. Colloquium Comput. Complex. TR98-014 (1998) arXiv:TR98-014"},{"key":"10202_CR8","doi-asserted-by":"crossref","unstructured":"Assmann, S.F., Peck, G.W., Sys\u0142o, M.M., Zak, J.: The bandwidth of caterpillars with hairs of length 1 and 2. SIAM J. Alg. Discrete Meth. 2(4), 387\u2013393 (1981)","DOI":"10.1137\/0602041"},{"key":"10202_CR9","first-page":"31","volume":"13","author":"JH Yan","year":"1997","unstructured":"Yan, J.H.: The bandwidth problem in cographs. Tamsui Oxford J. Math. Sci 13, 31\u201336 (1997)","journal-title":"Tamsui Oxford J. Math. Sci"},{"issue":"3","key":"10202_CR10","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/0403033","volume":"3","author":"DJ Kleitman","year":"1990","unstructured":"Kleitman, D.J., Vohra, R.: Computing the bandwidth of interval graphs. SIAM J. Discrete Math. 3(3), 373\u2013375 (1990)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"10202_CR11","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/j.jda.2008.11.001","volume":"7","author":"P Heggernes","year":"2009","unstructured":"Heggernes, P., Kratsch, D., Meister, D.: Bandwidth of bipartite permutation graphs in polynomial time. J. Discrete Algorithms 7(4), 533\u2013544 (2009)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"10202_CR12","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1137\/0601042","volume":"1","author":"JB Saxe","year":"1980","unstructured":"Saxe, J.B.: Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Alg. Discrete Meth. 1(4), 363\u2013369 (1980)","journal-title":"SIAM J. Alg. Discrete Meth."},{"key":"10202_CR13","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fellows, M.R., Hallett, M.T.: Beyond NP-completeness for problems of bounded width (extended abstract): hardness for the W hierarchy. In: Proc. of STOC 1994, pp. 449\u2013458 (1994)","DOI":"10.1145\/195058.195229"},{"key":"10202_CR14","doi-asserted-by":"crossref","unstructured":"Dregi, M.S., Lokshtanov, D.: Parameterized complexity of bandwidth on trees. In: Proc. of ICALP 2014, pp. 405\u2013416 (2014)","DOI":"10.1007\/978-3-662-43948-7_34"},{"issue":"50","key":"10202_CR15","doi-asserted-by":"publisher","first-page":"7001","DOI":"10.1016\/j.tcs.2011.09.011","volume":"412","author":"PA Golovach","year":"2011","unstructured":"Golovach, P.A., Heggernes, P., Kratsch, D., Lokshtanov, D., Meister, D., Saurabh, S.: Bandwidth on AT-free graphs. Theor. Comput. Sci. 412(50), 7001\u20137008 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"10202_CR16","doi-asserted-by":"crossref","unstructured":"Unger, W.: The complexity of the approximation of the bandwidth problem. In: Proc. of FOCS 1998, pp. 82\u201391 (1998)","DOI":"10.1109\/SFCS.1998.743431"},{"key":"10202_CR17","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Lee, J.R., Mendel, M., Naor, A.: Measured descent: A new embedding method for finite metrics. In: Proc. of FOCS 2004, pp. 434\u2013443 (2004)","DOI":"10.1109\/FOCS.2004.41"},{"key":"10202_CR18","doi-asserted-by":"crossref","unstructured":"Feige, U.: Coping with the NP-hardness of the graph bandwidth problem. In: Proc. of SWAT 2000, Berlin, pp. 10\u201319 (2000)","DOI":"10.1007\/3-540-44985-X_2"},{"key":"10202_CR19","doi-asserted-by":"crossref","unstructured":"Cygan, M., Pilipczuk, M.: Faster exact bandwidth. In: Proc. of WG 2008. Lecture Notes in Computer Science, vol. 5344, pp. 101\u2013109 (2008)","DOI":"10.1007\/978-3-540-92248-3_10"},{"issue":"1","key":"10202_CR20","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/2071379.2071387","volume":"8","author":"M Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M.: Even faster exact bandwidth. ACM Trans. Algorithms 8(1), 8\u20131814 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"40\u201342","key":"10202_CR21","doi-asserted-by":"publisher","first-page":"3701","DOI":"10.1016\/j.tcs.2010.06.018","volume":"411","author":"M Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M.: Exact and approximate bandwidth. Theor. Comput. Sci. 411(40\u201342), 3701\u20133713 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"4\u20135","key":"10202_CR22","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1016\/j.dam.2011.10.032","volume":"160","author":"M Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M.: Bandwidth and distortion revisited. Discrete Appl. Math. 160(4\u20135), 494\u2013504 (2012)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"10202_CR23","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1137\/100789403","volume":"26","author":"O Amini","year":"2012","unstructured":"Amini, O., Fomin, F.V., Saurabh, S.: Counting subgraphs via homomorphisms. SIAM J. Discrete Math. 26(2), 695\u2013717 (2012)","journal-title":"SIAM J. Discrete Math."},{"key":"10202_CR24","doi-asserted-by":"crossref","unstructured":"Feige, U., Talwar, K.: Approximating the bandwidth of caterpillars. In: Proc. of APPROX-RANDOM 2005, vol. 3624, pp. 62\u201373 (2005)","DOI":"10.1007\/11538462_6"},{"key":"10202_CR25","doi-asserted-by":"crossref","unstructured":"Vassilevska, V., Williams, R., Woo, S.L.M.: Confronting hardness using a hybrid approach. In: Proc. of SODA, pp. 1\u201310 (2006)","DOI":"10.1145\/1109557.1109558"},{"key":"10202_CR26","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.tcs.2013.03.024","volume":"511","author":"M F\u00fcrer","year":"2013","unstructured":"F\u00fcrer, M., Gaspers, S., Kasiviswanathan, S.P.: An exponential time 2-approximation algorithm for bandwidth. Theor. Comput. Sci. 511, 23\u201331 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"10202_CR27","unstructured":"M. Karpinski, M., Wirtgen, J., Zelikovsky, A.: An approximation algorithm for the bandwidth problem on dense graphs. Technical report (1997)"},{"key":"10202_CR28","doi-asserted-by":"crossref","unstructured":"Cygan, M., Pilipczuk, M.: Faster exact bandwidth. In: International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 101\u2013109 (2008). Springer","DOI":"10.1007\/978-3-540-92248-3_10"},{"key":"10202_CR29","doi-asserted-by":"crossref","unstructured":"D\u00edaz, J., Serna, M., Thilikos, D.M.: Counting h-colorings of partial k-trees. Theor. Comput. Sci. 281(1\u20132), 291\u2013309 (2002)","DOI":"10.1016\/S0304-3975(02)00017-8"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10202-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10202-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10202-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:48:25Z","timestamp":1744217305000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10202-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,25]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10202"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10202-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2025,1,25]]},"assertion":[{"value":"19 November 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing of interest"}}],"article-number":"10"}}