App oxima ing Layou P oblems
on Random Spa se G aphs∗
J. D´ıaz †J. Pe i †M. Se na†L. T e isan‡
Ma ch 7, 2001
Abs ac
We show ha , wi h high p obabili y, se e al layou p oblems a e app oximable
wi hin a cons an o andom g aphs d awn om he s anda d Gn,p model wi h p=c/n
o some cons an c. Ou esul s es ablish ha , in ac , any algo i hm ha e u ns a
easible solu ion will p oduce such an app oxima ion o g aphs wi h good expansion
p ope ies.
1 In oduc ion
Linea a angemen p oblems play an impo an ole in Compu e Science [27, 1, 8]. A
linea layou (o linea a angemen o e ex o de ing) o a g aph Gwi h nnodes is a
one- o-one mapping o he e ices o G o he se {1,...,n}. A layou πon G= (V, E)
de e mines in a unique way a nes ed sequence o e ex subse s con aining hose e ices
placed up o he i- h posi ion. The layou also induces an assignmen o leng hs o
e e y edge in he g aph: he leng h induced by a layou π o an edge e=u ∈Eis
λ(π, e) = |π(u)−π( )|. The complexi y o a g aph in e ms o a linea layou is usually
ob ained by measu ing leng h, c ossing edges o neighbo s placemen .
The bandwid h p oblem asks o a layou minimizing he maximum edge leng h. The
p oblem is NP-comple e [28], e en o ees wi h maximum deg ee 3 [14] o ca e pilla s
wi h hai leng h 3 [25]. I can be app oxima ed wi hin a cons an o some es ic ed
classes o ees [18], bu has no polynomial ime app oxima ion scheme o ees [4]. I has a
cons an andomized app oxima ion algo i hm o dense ins ances [21], and no polynomial
ime app oxima ion algo i hm o gene al g aphs [20].
The minimum cu a angemen asks o a layou minimizing he maximum cu along
he nes ed sequence o e ex se s. The p oblem is NP-comple e [17], e en o plana
g aphs wi h maximum deg ee 3 [26]. Fo ees he p oblem is in P[33] and e en in
NC [9]. I can be app oxima ed wi hin any cons an o dense g aphs [3]. A a ia ion
∗This esea ch was suppo ed by he ESPRIT Long Te m Resea ch P ojec No. 20244, ALCOM-IT
(WP 3.3) and CICYT p ojec TIC97-1475-CE. The i s and hi d au ho s we e also suppo ed by CIRIT
p ojec 1997SGR-00366.
†Depa amen de Llengua ges i Sis emes In o m`a ics, Uni e si a Poli `ecnica Ca alunya, Campus No d
C6, Jo di Gi ona Salgado 1-3, 08034 Ba celona, Spain. {diaz,jpe i ,mjse na}@lsi.upc.es
‡MIT Labo a o y o Compu e Science Room NE43-371, 545 Technology Squa e, Camb idge MA
02139-3594, USA. luca@ heo y.lcs.mi .edu
1
o he p oblem in which he cu excludes edges ouching he las e ex is known as
he minimum modi ied cu a angemen and is also NP-comple e o plana g aphs wi h
maximum deg ee 3 [26].
The minimum linea a angemen p oblem (also known as he minimum edge sum
[19] o he op imal linea o de ing [1]) seeks a layou ha minimizes he o al edge leng h.
This p oblem is also NP-comple e [16]. Fo ees he p oblem is in P[31] and in NC [9].
I can be app oxima ed wi hin a O(log2n) ac o using he app oxima e max low-min
cu heo em [23]. A be e app oxima ion ac o O(log nlog log n) can be achie ed using
sp eading me ics [13]. This esul has been imp o ed ecen ly o a O(log n) app oxima ion
o gene al g aphs and o a O(log log n) ac o o plana g aphs [30]. On he o he hand,
he p oblem can be app oxima ed wi hin a 1+ǫ ac o in ime nO(1/ǫ)when es ic ed
o dense g aphs using linea p og amming and andom ounding [3]. No hing is known
abou he ha dness o app oxima ing he minimum linea a angemen p oblem, which is
no e en known o be max-SNP-ha d. In [29] some heu is ics algo i hms o app oxima e
his p oblem a e empi ically s udied. The maximum linea a angemen p oblem ha asks
o a layou maximizing he o al edge leng h is no o p ac ical in e es , bu i is wo h
no ing ha i s app oximabili y p ope ies a e en i ely unde s ood: A g eedy algo i hm
can be used o ob ain an app oxima ion wi hin a ac o o 2 [11].
The e ex sepa a ion p oblem has he same o mula ion as he minimum cu a -
angemen p oblem, bu using as measu e he numbe o e ices in he i s pa i ion
connec ed o he second one. This measu e was i s in oduced in [7] as he δ-ope a o .
The p oblem is NP-comple e [24], bu in P o ees [12]. The global e sion in which one
looks o a layou minimizing he sum o all he sepa a ions is known as he minimal sum
cu p oblem [10] o he minimal p o ile p oblem [22]. The p oblem is equi alen o he
in e al g aph comple ion p oblem ha is also NP-comple e [15]. Fo ees he p oblem
is in P[22] and in NC [10]. An app oxima ion ac o O(log nlog log n) can be ob ained
using sp eading me ics [13].
The abo e esul s es ablish he di icul y in dealing wi h spa se g aphs. In gene al,
conside ing only dense ins ances makes a p oblem easie because such g aphs inhe i mos
o he good p ope ies o dense andom g aphs. In his pape we y o analyze he
di icul y o app oxima ing some o he abo e p oblems o andom spa se g aphs (d awn
om he s anda d Gn,p model wi h p=c/n [5, 2]) and expande s.
A na u al ques ion is o ask whe he he e is any ela ion be ween he app ox-
imabili y o he maximiza ion e sion o he p oblems, and whe he we can in e some
consequence o he minimiza ion e sion om ou unde s anding o hese maximiza ion
e sions. I hus makes sense o in oduce he gap be ween he maximum an he minimum
alues, he a io be ween he maximum and he minimum alues, and o es ima e his gap
alue o in e es ing classes o g aphs. No e ha whene e we can bound he gap o a
ce ain cons an >1, i ollows ha any a angemen o Gis -app oxima e o bo h he
minimiza ion and maximiza ion p oblems.
Fo ins ance, in he case o he minimum linea a angemen p oblem, i is clea ha
he gap is 1 o any comple e g aph G. Mo eo e , o a g aph ha has only one edge,
he gap is n(and his is he la ges possible gap). Those ex emal cases sugges ha he
gap o his p oblem is ela ed o he connec i i y p ope y o a g aph, and hus i seems
unlikely ha we can ind a bounded deg ee g aph wi h a small gap alue, and one would
hing ha , a leas , almos all (in he p obabilis ic sense) spa se g aphs ha e a la ge gap
alue. We will show ha he opposi e esul s hold.
2
2 De ini ions and basic esul s
Conside an undi ec ed g aph G= (V, E) wi h n=|V| e ices and m=|E|edges. We
deno e by N(u) he se o neighbo s o a e ex uincluding u. A layou o Gis any
bijec i e unc ion ha associa es o each e ex a numbe in he ange {1,... ,n}= [n].
Gi en a layou π o G, o any i∈[n] conside he se s L(i) = { |π( )≤i}and
R(i) = { |π( )> i}. Fo a gi en layou π, de ine
λ(e, π) = |π(u)−π( )|e=u ∈E
cu (i, π) = |{u ∈E|u∈L(i)∧ ∈R(i)}| i∈[n]
mod-cu (i, π) = |{u ∈E|u∈L(i)− {i} ∧ ∈R(i)}| i∈[n]
δ(i, π) = |{u∈L(i)| ∃w∈R(i) : (u, w)∈E}| i∈[n]
De ini ion 1. The o mal de ini ions o he p oblems we s udy a e he ollowing:
•Minimum linea a angemen (minla). Gi en a g aph G= (V, E), ind a layou π
ha minimizes
la(G, π) =
n−1
X
i=1
cu (i, π) = X
e∈E
λ(e, π).
•Minimum sum modi ied cu (minmla). Gi en a g aph G= (V, E), ind a layou π
ha maximizes
mla(G, π) =
n−1
X
i=1
mod-cu (i, π).
•Minimum sum cu (minsc). Gi en a g aph G= (V, E), ind a layou π ha minimizes
sc(G, π) =
n−1
X
i=1
δ(i, π).
We will also conside he maximiza ion e sions o such p oblems, namely he max-
imum linea a angemen (maxla), he maximum sum modi ied cu (maxmla), and he
maximum sum cu (maxsc). Fo sake o simplici y, o a gi en measu e F, we will use he
no a ions
maxF(G) = max
πF(G, π)
minF(G) = min
πF(G, π)
a F(G) = PπF(G, π)
n!
o deno e i s maximum, minimum and a e age alues.
De ini ion 2. Fo a measu e F, we de ine he gap be ween he minimum and maximum
alues as
gapF(G) = maxF(G)
minF(G)= 1 + maxF(G)−minF(G)
minF(G).
3
De ini ion 3. Gi en a cons an , an algo i hm Ais an -app oxima ion o a minimiza-
ion (maximiza ion) p oblem o a unc ion Fwhen i holds ha o any g aph G
A(G)
minF(G)≤1 + maxF(G)
A(G)≤1 + .
Equi alen ly, he alue ǫ= 1 − is called he app oxima ion a io o he -app oxima e
algo i hm A[15]. Obse e ha any bound on he second exp ession in ou de ini ion gi es
a bound on he app oxima ion a io o any algo i hm ha compu es a layou o G.
Basic esul s. Gi en a g aph G= (V, E) wi h nnodes and medges, i is well known ha
he a e age leng h o an edge e=u is (n+1)/3. Taking in o accoun ha la(G, π) is he
sum o all edge leng hs we ha e a la(G)≥m(n+1)/3. To bound he a e age modi ied cu
cos we use he ollowing s aigh o wa d ela ionship: mla(G, π)+P ∈Vd( )≥la(G, π).
The same ela ionship holds o he a e age alue and we ha e ha a mla(G)≥m(n−
5)/3.
To analyze he a e age sum cu cos we conside a simpli ied measu e. Gi en a
g aph G= (V, E) each e ex uselec s a neighbo s(u)6=ui any, o an isola ed e ex
se s(u) = u. We will use an a b i a y (bu ixed) selec ion s. Gi en a layou πde ine
D(G, π) = P ∈Vmax(0, π( )−π(s( ))). No ice ha o all π,sc(G, π)≥D(G, π).
Fu he mo e he expec ed con ibu ion o he edge ( , s( )) is 0 wi h p obabili y 1/2 and
(n+ 1)/3 wi h p obabili y 1/2, ha is (n+ 1)/6. Adding up o all e ices we ge
a sc(G)≥n(n+ 1)/6.
3 The g aphs
We in oduce now wo g aph classes ha cap u e he p ope ies needed o bound he gap.
De ini ion 4 (Mixing g aphs). Le 0 < γ, ǫ < 1 and c > 0. A g aph G= (V, E) wi h
|V|=nand |E|=mis said o be (ǫ, γ, c)-mixing i o any wo disjoin se s A, B ⊆V
such ha |A| ≥ ǫn,|B| ≥ ǫn, i is he case ha
θ(A, B)−c
n· |A||B|≤γc
n· |A||B|,
whe e θ(A, B) is he numbe o edges o Gha ing one endpoin in Aand ano he in B.
De ini ion 5 (Dispe se g aphs). Le 0 < ǫ < 1. A g aph G= (V, E) wi h |V|=n
and |E|=mis said o be an ǫ-dispe se i o any wo disjoin se s A, B ⊆Vsuch ha
|A| ≥ ǫn, and |B| ≥ ǫn he e is a leas an edge ha ing an endpoin in Aand an endpoin
in B.
I is known ha explici cons uc ions o expande g aphs imply e icien cons uc ion
o mixing g aphs. In pa icula , he ollowing esul holds.
Theo em 1 (See e.g. [6]). A cons an αexis s such ha o any ǫ, γ > 0, o any n
and any d≥α/(ǫ2γ2), an (ǫ, γ, m/n)-mixing g aph wi h maximum deg ee a mos dcan
be cons uc ed in poly(n) ime.
Rema k ha om he de ini ion o mixing and dispe se g aphs, i ollows ha ,
any (ǫ, γ, c)-mixing g aph is also an ǫ-dispe se , and so Theo em 1 also gi es an explici
cons uc ion o dispe se g aphs.
4
Theo em 2. A cons an βexis s such ha o any ǫ > 0, o any nand any d≥β/ǫ2,
an ǫ-dispe se g aph wi h n e ices and maximum deg ee a mos dcan be cons uc ed in
poly(n) ime.
De ini ion 6 (Random spa se g aphs [5, 2]). We conside he s anda d class o an-
dom g aphs Gn,p which ha e nnodes and each po en ial edge exis s wi h p obabili y p.
Al hough he andom spa se g aphs conside ed in his pape a e expec ed o be non
connec ed, wi h high p obabili y hey ha e good mixing p ope ies.
Lemma 1 (Che no bounds). Le X1,... ,Xnbe independen andom a iables whose
ange is {0,1}. Le µ=E[Pn
i=1 Xi]. Then o any 0< γ < 1i is he case ha
P "(1 −γ)µ≤
n
X
i=1
Xi≤(1 + γ)µ#≥1−2 exp(−γ2µ/3).
Theo em 3 (Random g aphs a e mixing). Fo any ǫ, γ > 0, o any c≥3.296
ǫ2γ2, an-
dom g aphs d awn om Gn,p wi h p=c/n a e (ǫ, γ, c)-mixing wi h p obabili y a leas
1−2−Ω(n).
P oo . Conside any wo se s A, B ⊆Vsuch ha |A|,|B| ≥ ǫn. The e a e k=|A||B|
possible edges ha ing an endpoin in Aand an endpoin in B. Le us call Y1,... ,Yk he
andom a iables such ha Yi= 1 i he i- h (in lexicog aphical o de ) o such edges is in
he g aph, and Yi= 0 o he wise. The a e age o Pk
i=1 Yiis clea ly µ=c|A||B|/n. Then
we ha e ha
P "(1 −γ)µ≤
k
X
i=1
Yi≤(1 + γ)µ#≥1−exp(γ2µ
3+ 1).
Since he e a e a mos 3nchoices o he se s Aand B, i ollows ha he p obabili y
ha he g aph is no mixing is a mos
exp (ln 3)n−γ2c|A| |B|
n
1
3−1.
No e ha he e m in he exponen is
nln 3 −cγ2ǫ21
3−1/n≤ −Ω(n).
As mixing g aphs a e dispe se s, we also ha e ha andom g aphs a e dispe se
g aphs wi h high p obabili y.
4 Bounding he Gap
Now we bound he gap be ween he maximum and minimum cos s o mixing g aphs.
5

Lemma 2. Le G= (V, E)be an (ǫ, γ, c)-mixing g aph (wi h 0<ǫ, γ <1), hen
gapla(G)≤1 + 1
1−γ6ǫ
1−6ǫ(1 + γ) + 2γ= 1 + O(ǫ+γ).
P oo . Le πbe any layou o G. We will bound i s cos om abo e and om below:
la(G, π) =
n−1
X
i=1
cu (i, π)≥
n−ǫn
X
i=ǫn
cu (i, π)≥(1 −γ)c
n
n−ǫn
X
i=ǫn
i(n−i).
Fo he lowe bound,
la(G, π) =
n−1
X
i=1
cu (i, π)≤2ǫmn +
n−ǫn
X
i=ǫn
cu (i, π)≤2ǫmn + (1 + γ)c
n
n−ǫn
X
i=ǫn
i(n−i).
The e o e, le ing S=c
nPn−ǫn
i=ǫn i(n−i), we ha e
maxla(G)≤2ǫmn + (1 + γ)S,
minla(G)≥(1 −γ)S,
maxla(G)−minla(G)≤2ǫmn + 2γS.
As a la ≥m(n+ 1)/3 he e is a layou ha gi es a leas his alue so,
2ǫmn + (1 + γ)S≥m(n+ 1)
3>mn
3
he e o e 2ǫmn ≤6ǫ
1−6ǫ(1 + γ)Sand we ge
gapla(G)≤1 + 6ǫ
1−6ǫ(1 + γ)S+ 2γS
(1 −γ)S.
A simila esul holds o he minimum sum modi ied cu p oblem.
Lemma 3. Le G= (V, E)be an (ǫ, γ, c)-mixing g aph (wi h 0< ǫ, γ < 1) wi h |V|>9.
Then
gapmla(G)≤1 + 1
1−γ12ǫ
1−12ǫ(1 + γ) + 2γ= 1 + O(ǫ+γ).
P oo . Le πbe any a angemen . We will bound i s cos om abo e and om below:
mla(G, π) =
n−1
X
i=1
mod-cu (i, π)≥
n−ǫn−1
X
i=ǫn+1
mod-cu (i, π)≥(1 −γ)c
m
n−ǫn−1
X
i=ǫn+1
(i−1)(n−i).
Fo he lowe bound,
mla(G, π) =
n−1
X
i=1
cu (i, π)≤2(ǫn + 1)m+
n−ǫn−1
X
i=ǫn+1
mod-cu (i, π)
≤2ǫnm + (1 + γ)c
n
n−ǫn−1
X
i=ǫn+1
(i−1)(n−i)
6
whe e he las inequali y holds because mod-cu (1, π) = mod-cu (n, π) = 0 o any layou
π. The e o e, le ing T=c
nPn−ǫn−1
i=ǫn+1 (i−1)(n−i), we ha e
maxmla(G)≤2ǫnm + (1 + γ)T,
minmla(G)≥(1 −γ)T,
maxmla(G)−minmla(G, π)≤2ǫnm + 2γT.
As a mla =m(n−5)/3 he e is a layou ha gi es a leas his alue so,
2ǫnm + (1 + γ)T≥m(n−5)
3
and as n > 9 i holds ha n−5≥n/2. The e o e 2ǫnm + (1 + γ)T≥mn
6and we ge
2ǫnm ≤12ǫ
1−12ǫ(1 + γ)T.
A simila esul s holds o he minimum sum cu p oblem.
Lemma 4. Le G= (V, E)be an ǫ-dispe se g aph (wi h ǫ < 1), hen
gapsc(G)≤1
1−4ǫ.
P oo . We ind lowe and uppe bounds o he alue sc(G). We i s no ice ha in an
ǫ-dispe se g aph i is he case ha δ(π, i)≥i−ǫn o e e y ǫn < i < n −ǫn. This is
because he e canno be ǫn e ices on he le o iand ǫn e ices on he igh o iwi hou
any connec ion.
sc(G, π) =
n−1
X
i=1
δ(π, i)≥
n−ǫn
X
i=ǫn
δ(π, i)≥
n−ǫn
X
i=1
(i−ǫn)
>(n−ǫn)2/2−ǫn(n−ǫn)> n2/2−2ǫn2.
Fo he uppe bound, we ge
sc(G, π) =
n−1
X
i=1
δ(π, i)≤
n−1
X
i=1
i= (n−1)n/2≤n2/2.
Thus, we ha e minsc(G)≥n2/2−2ǫn2and maxsc(G)≤n2/2 and hus gapsc ≤1
1−4ǫ.
Consequen ly, we ha e es ablished he ollowing heo em:
Theo em 4. The p oblems minla and minmla can be app oxima ed wi hin a cons an
on mixing g aphs. The minsc p oblem can be app oxima ed wi hin a cons an on dispe se
g aphs. Fu he mo e, he e exis s a cons an csuch ha o any α > 0, o any n,
P [gapF(G)>1 + α]≤2−n
whe e Gis a andom g aph om he Gn,p model wi h p=c
α4n, and Fis any o he h ee
measu es la,mla,sc.
7
5 Conclusions
Simila esul s can be achie ed o he local p oblems such as bandwid h, mincu layou
and e ex sepa a ion. Fo he bandwid h p oblem ixing any layou and aking he se s
o med by he i s ǫn e ices and he las ǫn e ices, in an (ǫ, γ, c)-mixing g aph we ha e
a leas one edge connec ing bo h pa i ions, and he e o e a lowe bound o he layou
bandwid h o (1 −2ǫ)n. In he case ha ǫ < 1/3 we ha e a 3 app oxima ion. A simila
esul o he bandwid h minimiza ion is gi en in [32].
In an (ǫ, γ, c)-mixing g aph we ha e a leas (1 −γ)cn/4 edges in he cen al cu .
This is a lowe bound o he p oblem mincu . The bound also applies o he bisec ion
p oblem, because he cen al cu spli s he g aph in o wo equal sized se s. I also applies
o he max cu p oblem. The e o e we can app oxima e hose p oblems wi hin a cons an ,
o such g aphs.
In an (ǫ)-dispe se mixing g aph we ha e a leas (1/2−ǫ)nnodes in he cen al cu .
So, o nla ge enough we ge a cons an app oxima ion o he e ex sepa a ion p oblem.
I is wo h o ema k ha he ob ained esul s gi e he app oxima ion ega dless
he connec i i y o he g aph. Fo his class o g aphs, o ge a cons an app oxima ion,
i is no necessa y o inish o a connec ed componen be o e s a ing a new one.
A s anda d way o e alua ing he eal e iciency ( om a p ac ical poin o iew) o
an algo i hm is o e alua e i s pe o mance on andom ins ances. Ou esul s show ha
any algo i hm compu ing a layou , no ma e how bad (o good), will pe o m e y well
on andom spa se g aphs, poin ing ou ha such e alua ions may be unwo hy o some
p oblems.
Re e ences
[1] D. Adolphson and T. C. Hu. Op imal linea o de ing. SIAM J. on Applied Ma he-
ma ics, 25(3):403–423, No embe 1973.
[2] N. Alon and J.H. Spence . The p obabilis ic me hod. Wiley-In e science Se ies in
Disc e e Ma hema ics and Op imiza ion. John Wiley & Sons Inc., New Yo k, 1992.
Wi h an appendix by P. E d˝os, A Wiley-In e science Publica ion.
[3] S. A o a, A. F ieze, and H. Kaplan. A new ounding p ocedu e o he assignmen
p oblem wi h applica ions o dense g aphs a angemen s. In 37 h IEEE Symposium
on Founda ions o Compu e Science, 1996.
[4] G. Blache, M. Ka pinski, and J. Wi gen. On app oxima ion in ac abili y o he
bandwid h p oblem. Technical Repo TR98-014, Elec onic Colloquium on Compu-
a ional Complexi y, 1998.
[5] B. Bollob´as. Random g aphs. Academic P ess Inc. [Ha cou B ace Jo ano ich Pub-
lishe s], London, 1985.
[6] P. C escenzi, R. Sil es i, and L. T e isan. To weigh o no o weigh : Whe e is
he ques ion? In 4 h IEEE Is ael Symposium on Theo y o Compu ing and Sys ems,
pages 68–77, 1996.
8
[7] J. D´ıaz. The δ-ope a o . In L. Budach, edi o , Fundamen als o Compu a ion Theo y,
pages 105–111. Akademie-Ve lag, 1979.
[8] J. D´ıaz. G aph layou p oblems. In I. M. Ha el and V. Koubek, edi o s, Ma hema ical
Founda ions o Compu e Science, olume 629, pages 14–24. Sp inge -Ve lag, Lec u e
No es in Compu e Science, 1992.
[9] J. D´ıaz, A. Gibbons, G. Pan ziou, M. Se na, P. Spi akis, and J. To ´an. Pa allel
algo i hms o he minimum cu and he minimum leng h ee layou p oblems. The-
o e ical Compu e Science, (181):267–287, 1997.
[10] J. D´ıaz, A. M. Gibbons, M. S. Pa e son, and J. To ´an. The minsumcu p oblem. In
F. Dehen, R. J. Sack, and N. San o o, edi o s, Algo i hms and Da as uc u e, olume
519, pages 65–79. Lec u e No es in Compu e Science, 1991.
[11] J. D´ıaz, M. J. Se na, and P. Spi akis. Some ema ks on he app oximabili y o g aph
layou p oblems. Technical Repo LSI 94-16-R, Uni e si a Poli `ecnica de Ca alunya,
1994.
[12] J. Ellis, I. H. Sudbo ough, and J. Tu ne . The e ex sepa a ion and sea ch numbe
o a g aph. In o ma ion and Compu a ion, (113):50–79, 1979.
[13] G. E en, J. Nao , S. Rao, and B. Schiebe . Di ide and conque app oxima ion algo-
i hms ia sp eading me ics. In 36 h IEEE Symposium on Founda ions o Compu e
Science, pages 62–71, 1995.
[14] M. R. Ga ey, R. L. G aham, D. S. Johnson, and D. Knu h. Complexi y esul s o
bandwid h minimiza ion. SIAM J on Applied Ma hema ics, 34:477–495, Sep embe
1978.
[15] M. R. Ga ey and D. S. Johnson. Compu e s and In ac abili y: A Guide o he Theo y
o NP-Comple eness. F eeman, San F ancisco, 1979.
[16] M. R. Ga ey, D. S. Johnson, and L. S ockmeye . Some simpli ied NP-comple e g aph
p oblems. Theo e ical Compu e Science, 1:237–267, 1976.
[17] F. Ga il. Some NP-comple e p oblems on g aphs. In P oc. 11 h. Con . on In o ma-
ion Sciences and Sys ems, pages 91–95, John Hopkins Uni ., Bal imo e, 1977.
[18] J. Ha alambides and F. Makedon. App oxima ion algo i hms o he bandwid h mini-
miza ion p oblem o a la ge class o ees. Theo y o Compu ing Sys ems, (30):67–90,
1997.
[19] L. H. Ha pe . Op imal numbe ings and isope ime ic p oblems on g aphs. Jou nal
o Combina o ial Theo y, 1(3):385–393, 1966.
[20] M. Ka pinski and J. Wi gen. On app oxima ion ha dness o he bandwid h p oblem.
Technical Repo TR97-041, Elec onic Colloquium on Compu a ional Complexi y,
1997.
[21] M. Ka pinski, J. Wi gen, and A. Zeliko sky. An app oxima ing algo i hm o he
bandwid h p oblem on dense g aphs. Technical Repo TR 97-017, ECCC, 1997.
9