Line-Distortion, Bandwidth and Path-Length of a Graph

详细信息    查看全文

• 作者：Feodor F. Dragan (17)
  Ekkehard K?hler (18)
  Arne Leitert (17)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8503
• 期：1
• 页码：158-169
• 参考文献：1. Blache, G., Karpinski, M., Wirtgen, J.: On approximation intractability of the bandwidth problem, Technical report TR98-014, University of Bonn (1997)
  2. B?doiu, M., Chuzhoy, J., Indyk, P., Sidiropoulos, A.: Low-distortion embeddings of general metrics into the. In: STOC 2005, pp. 225-33. ACM (2005)
  3. Bǎdoiu, M., Dhamdhere, K., Gupta, A., Rabinovich, Y., Raecke, H., Ravi, R., Sidiropoulos, A.: Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In: SODA 2005, pp. 119-28. ACM/SIAM (2005)
  4. Corneil, D.G., Olariu, S., Stewart, L.: Asteroidal Triple-Free Graphs. SIAM Journal on Discrete Mathematics?10, 399-30 (1997) CrossRef
  5. Dourisboure, Y., Gavoille, C.: Tree-decompositions with bags of small diameter. Discr. Math.?307, 208-29 (2007) CrossRef
  6. Dragan, F.F., K?hler, E.: An Approximation Algorithm for the Tree / t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) RANDOM 2011 and APPROX 2011. LNCS, vol.?6845, pp. 171-83. Springer, Heidelberg (2011) CrossRef
  7. Feige, U.: Approximating the bandwidth via volume respecting embedding. J. of Computer and System Science?60, 510-39 (2000) CrossRef
  8. Fellows, M.R., Fomin, F.V., Lokshtanov, D., Losievskaja, E., Rosamond, F.A., Saurabh, S.: Distortion Is Fixed Parameter Tractable. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.?5555, pp. 463-74. Springer, Heidelberg (2009) CrossRef
  9. Fomin, F.V., Lokshtanov, D., Saurabh, S.: An exact algorithm for minimum distortion embedding. Theor. Comput. Sci.?412, 3530-536 (2011) CrossRef
  10. Golovach, P.A., Heggernes, P., Kratsch, D., Lokshtanov, D., Meister, D., Saurabh, S.: Bandwidth on AT-free graphs. Theor. Comput. Sci.?412, 7001-008 (2011) CrossRef
  11. Gupta, A.: Improved Bandwidth Approximation for Trees and Chordal Graphs. J. Algorithms?40, 24-6 (2001) CrossRef
  12. Heggernes, P., Kratsch, D., Meister, D.: Bandwidth of bipartite permutation graphs in polynomial time. Journal of Discrete Algorithms?7, 533-44 (2009) CrossRef
  13. Heggernes, P., Meister, D.: Hardness and approximation of minimum distortion embeddings. Information Processing Letters?110, 312-16 (2010) CrossRef
  14. Heggernes, P., Meister, D., Proskurowski, A.: Computing minimum distortion embeddings into a path of bipartite permutation graphs and threshold graphs. Theoretical Computer Science?412, 1275-297 (2011) CrossRef
  15. Indyk, P., Matousek, J.: Low-distortion embeddings of finite metric spaces. In: Handbook of Discrete and Computational Geometry, pp. 177-96. CRC (2004)
  16. Kloks, T., Kratsch, D., Müller, H.: Approximating the Bandwidth for Asteroidal Triple-Free Graphs. J. Algorithms?32, 41-7 (1999) CrossRef
  17. Kratsch, D., Stewart, L.: Approximating Bandwidth by Mixing Layouts of Interval Graphs. SIAM J. Discrete Math.?15, 435-49 (2002) CrossRef
  18. Monien, B.: The Bandwidth-Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete. SIAM J. Alg. Disc. Meth.?7, 505-12 (1986) CrossRef
  19. R?cke, H.: http://ttic.uchicago.edu/~harry/teaching/pdf/lecture15.pdf
  20. Robertson, N., Seymour, P.: Graph minors. I. Excluding a forest. Journal of Combinatorial Theory, Series B?35, 39-1 (1983) CrossRef
  21. Tenenbaum, J.B., de Silva, V., Langford, J.C.: A global geometric framework for nonlinear dimensionality reduction. Science?290, 2319-323 (2000) CrossRef
  
• 作者单位：Feodor F. Dragan (17)
  Ekkehard K?hler (18)
  Arne Leitert (17)
  
  17. Department of Computer Science, Kent State University, Kent, OH, 44242, USA
  18. Mathematisches Institut, Brandenburgische Technische Universit?t Cottbus, D-03013, Cottbus, Germany
  
• ISSN：1611-3349

文摘

We investigate the minimum line-distortion and the minimum bandwidth problems on unweighted graphs and their relations with the minimum length of a Robertson-Seymour’s path-decomposition. The length of a path-decomposition of a graph is the largest diameter of a bag in the decomposition. The path-length of a graph is the minimum length over all its path-decompositions. In particular, we show: (i) if a graph G can be embedded into the line with distortion k, then G admits a Robertson-Seymour’s path-decomposition with bags of diameter at most k in G; (ii) for every class of graphs with path-length bounded by a constant, there exist an efficient constant-factor approximation algorithm for the minimum line-distortion problem and an efficient constant-factor approximation algorithm for the minimum bandwidth problem; (iii) there is an efficient 2-approximation algorithm for computing the path-length of an arbitrary graph; (iv) AT-free graphs and some intersection families of graphs have path-length at most 2; (v) for AT-free graphs, there exist a linear time 8-approximation algorithm for the minimum line-distortion problem and a linear time 4-approximation algorithm for the minimum bandwidth problem.