Top

Published in:

2015 | OriginalPaper | Chapter

Minimum Linear Arrangement of Series-Parallel Graphs

Authors : Martina Eikel, Christian Scheideler, Alexander Setzer

Published in: Approximation and Online Algorithms

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present a factor \(14D^2\) approximation algorithm for the minimum linear arrangement problem on series-parallel graphs, where \(D\) is the maximum degree in the graph. Given a suitable decomposition of the graph, our algorithm runs in time \(O(|E|)\) and is very easy to implement. Its divide-and-conquer approach allows for an effective parallelization. Note that a suitable decomposition can also be computed in time \(O(|E|\log {|E|})\) (or even \(O(\log {|E|}\log ^*{|E|})\) on an EREW PRAM using \(O(|E|)\) processors).

For the proof of the approximation ratio, we use a sophisticated charging method that uses techniques similar to amortized analysis in advanced data structures.

On general graphs, the minimum linear arrangement problem is known to be NP-hard. To the best of our knowledge, the minimum linear arrangement problem on series-parallel graphs has not been studied before.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Online Ad Assignment with an Ad Exchange

next chapter Online Dual Edge Coloring of Paths and Trees

Adolphson, D., Hu, T.C.: Optimal linear ordering. SIAM J. Appl. Math. 25(3), 403–423 (1973)CrossRefMATHMathSciNet

Adolphson, D.L.: Single machine job sequencing with precedence constraints. SIAM J. Comput. 6(1), 40–54 (1977)CrossRefMATHMathSciNet

Ambühl, C., Mastrolilli, M., Svensson, O.: Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constrained scheduling. In: Proceedings of FOCS, pp. 329–337. IEEE Computer Society (2007)

Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2), 5 (2009)CrossRefMathSciNet

Bodlaender, H.L., de Fluiter, B.: Parallel algorithms for series parallel graphs. In: Diaz, J., Serna, M. (eds.) ESA 1996. LNCS, vol. 1136, pp. 277–289. Springer, Heidelberg (1996) CrossRef

Charikar, M., Hajiaghayi, M.T., Karloff, H., Rao, S.: L22 spreading metrics for vertex ordering problems. In: Proceedings of SODA, pp. 1018–1027. Society for Industrial and Applied Mathematics, Philadelphia (2006)

Chung, F.R.K.: Labelings of graphs. In: Beineke, L., Wilson, R. (eds.) Selected Topics in Graph Theory, vol. 3, pp. 151–168. Academic Press, New York (1988)

Cohen, J., Fomin, F.V., Heggernes, P., Kratsch, D., Kucherov, G.: Optimal linear arrangement of interval graphs. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 267–279. Springer, Heidelberg (2006) CrossRef

Díaz, J., Petit, J., Serna, M.: A survey of graph layout problems. ACM Comput. Surv. 34(3), 313–356 (2002)CrossRef

10.

Eikel, M., Scheideler, C., Setzer, A.: Minimum linear arrangement of series-parallel graphs (full paper). ArXiv e-prints, October 2014

11.

Eppstein, D.: Parallel recognition of series-parallel graphs. Inf. Comput. 98(1), 41–55 (1992)CrossRefMATHMathSciNet

12.

Even, S., Shiloach, Y.: NP-completeness of several arrangement problems. Department of Computer Science, Technion, Haifa, Israel, Technical Report 43 (1975)

13.

Feige, U., Lee, J.R.: An improved approximation ratio for the minimum linear arrangement problem. Inf. Process. Lett. 101(1), 26–29 (2007)CrossRefMATHMathSciNet

14.

Fishburn, P., Tetali, P., Winkler, P.: Optimal linear arrangement of a rectangular grid. Discret. Math. 213(1–3), 123–139 (2000)CrossRefMATHMathSciNet

15.

Frederickson, G.N., Hambrusch, S.E.: Planar linear arrangements of outerplanar graphs. IEEE Trans. Circ. Syst. 35(3), 323–333 (1988)CrossRefMATHMathSciNet

16.

Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1(3), 237–267 (1976)CrossRefMATHMathSciNet

17.

Hadlock, F.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. 4(3), 221–225 (1975)CrossRefMATHMathSciNet

18.

Harper, L.H.: Optimal assignments of numbers to vertices. J. SIAM 12(1), 131–135 (1964)MATHMathSciNet

19.

Kikuno, T., Yoshida, N., Kakuda, Y.: A linear algorithm for the domination number of a series-parallel graph. Discret. Appl. Math. 5(3), 299–311 (1983)CrossRefMATHMathSciNet

20.

Macmahon, P.A.: The combination of resistances. Electrician 28, 601–602 (1892)

21.

Nakano, K.: Linear layouts of generalized hypercubes. In: van Leeuwen, J. (ed.) WG 1993. LNCS, vol. 790, pp. 364–375. Springer, Heidelberg (1994) CrossRef

22.

Petit, J.: Experiments on the minimum linear arrangement problem. J. Exp. Algorithmics 8, 2–3 (2003)CrossRefMathSciNet

23.

Petit, J.: Addenda to the survey of layout problems. Bull. EATCS 3(105), 177–201 (2013)MathSciNet

24.

Rao, S., Richa, A.W.: New approximation techniques for some ordering problems. In: Proceedings of SODA, pp. 211–218. Society for Industrial and Applied Mathematics, Philadelphia (1998)

25.

Rostami, H., Habibi, J.: Minimum linear arrangement of chord graphs. Appl. Math. Comput. 203(1), 358–367 (2008)CrossRefMATHMathSciNet

26.

Setzer, A.: The planar minimum linear arrangement problem is different from the minimum linear arrangement problem. ArXiv e-prints, September 2014

27.

Shahrokhi, F., Sýkora, O., Székely, L., Vrto, I.: On bipartite drawings and the linear arrangement problem. SIAM J. Comput. 30(6), 1773–1789 (2001)CrossRefMATHMathSciNet

28.

Takamizawa, K., Nishizeki, T., Saito, N.: Linear-time computability of combinatorial problems on series-parallel graphs. J. ACM 29(3), 623–641 (1982)CrossRefMATHMathSciNet

29.

Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. In: Proceedings of STOC, pp. 1–12. ACM, New York (1979)

Title: Minimum Linear Arrangement of Series-Parallel Graphs
Authors: Martina Eikel
Christian Scheideler
Alexander Setzer
Publisher: Springer International Publishing
Book: Approximation and Online Algorithms
Print ISBN: 978-3-319-18262-9

Electronic ISBN: 978-3-319-18263-6

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-319-18263-6_15

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner