[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

The Linear Arrangement Problem Parameterized Above Guaranteed Value

  • Conference paper
Algorithms and Complexity (CIAC 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3998))

Included in the following conference series:

Abstract

A linear arrangement (LA) is an assignment of distinct integers to the vertices of a graph. The cost of an LA is the sum of lengths of the edges of the graph, where the length of an edge is defined as the absolute value of the difference of the integers assigned to its ends. For many application one hopes to find an LA with small cost. However, it is a classical NP-complete problem to decide whether a given graph G admits an LA of cost bounded by a given integer. Since every edge of G contributes at least one to the cost of any LA, the problem becomes trivially fixed-parameter tractable (FPT) if parameterized by the upper bound of the cost. Fernau asked whether the problem remains FPT if parameterized by the upper bound of the cost minus the number of edges of the given graph; thus whether the problem is FPT “parameterized above guaranteed value.” We answer this question positively by deriving an algorithm which decides in time O(m + n + 5.88k) whether a given graph with m edges and n vertices admits an LA of cost at most m + k (the algorithm computes such an LA if it exists). Our algorithm is based on a procedure which generates a problem kernel of linear size in linear time for a connected graph G. We also prove that more general parameterized LA problems stated by Serna and Thilikos are not FPT, unless P = NP.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Cesati, M.: Compendium of parameterized problems (September 2005), http://bravo.ce.uniroma2.it/home/cesati/research/compendium.pdf

  2. Chung, F.R.K.: On optimal linear arrangements of trees. Comp. & Maths. with Appls. 10, 43–60 (1984)

    Article  MATH  Google Scholar 

  3. Diestel, R.: Graph Theory, 2nd edn. Springer, New York (2000)

    Google Scholar 

  4. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)

    Google Scholar 

  5. Estivill-Castro, V., Fellows, M.R., Langston, M.A., Rosamond, F.A.: FPT is P-Time extremal structure I. In: Broersma, H., Johnson, M., Szeider, S. (eds.) Algorithms and Complexity in Durham 2005, Proceedings of the first ACiD Workshop. Texts in Algorithmics, vol. 4, pp. 1–41. King’s College Publications (2005)

    Google Scholar 

  6. Fernau, H.: Parameterized Algorithmics: A Graph-theoretic Approach. Habilitation thesis, U. Tübingen (2005)

    Google Scholar 

  7. Fernau, H.: Parameterized Algorithmics for Linear Arrangement Problems. Talk at Dagstuhl (July 2005), slides at: http://www.dagstuhl.de/files/Materials/05/05301/05301.FernauHenning.Slides.pdf

  8. Fernau, H.: Parameterized Algorithmics for Linear Arrangement Problems (manscript) (July 2005), http://homepages.feis.herts.ac.uk/~comrhf/papers/ola.pdf

  9. Flum, J., Grohe, M.: Describing parameterized complexity classes. Information and Computation 187, 291–319 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  10. Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)

    Google Scholar 

  11. Garey, M.R., Johnson, D.R.: Computers and Intractability. W.H. Freeman & Comp., New York (1979)

    MATH  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  13. Goldberg, M.K., Klipker, I.A.: Minimal placing pf trees on a line. Tech. Report, Physico-Technical Institute of Low Temperatures, Ukranian SSR Acad. of Sciences, USSR (1976) (in Russian)

    Google Scholar 

  14. Harper, L.H.: Optimal assignments of numbers to vertices. J. Soc. Indust. Appl. Math. 12, 131–135 (1964)

    Article  MATH  MathSciNet  Google Scholar 

  15. Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31, 335–354 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  16. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (forthcoming, 2006)

    Google Scholar 

  17. Shiloach, Y.: A minimum linear arrangement algorithm for undirected trees. SIAM J. Comp. 8, 15–32 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  18. Serna, M., Thilikos, D.M.: Parameterized complexity for graph layout problems. EATCS Bulletin 86, 41–65 (2005)

    MATH  MathSciNet  Google Scholar 

  19. Tarjan, R.E.: Depth first search and linear graph algorithms. SIAM J. Comput. 1, 146–160 (1972)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gutin, G., Rafiey, A., Szeider, S., Yeo, A. (2006). The Linear Arrangement Problem Parameterized Above Guaranteed Value. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds) Algorithms and Complexity. CIAC 2006. Lecture Notes in Computer Science, vol 3998. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758471_34

Download citation

  • DOI: https://doi.org/10.1007/11758471_34

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-34375-2

  • Online ISBN: 978-3-540-34378-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics