scientific article; zbMATH DE number 2079381

MaRDI QIDQ4471340zbMATH OpenFDO

Authors Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair

Publication date 28 July 2004

zbMATH Keywords

polynomial time approximation schemesNP-hard optimization problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Embedding k-Outerplanar Graphs into l1
• \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees
• k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees
• Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs
• Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs

Cited in

(16)

• scientific article; zbMATH DE number 1107731 (Why is no real title available?)
• k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees
• On average distortion of embedding metrics into the line
• Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems
• A tight bound on approximating arbitrary metrics by tree metrics
• scientific article; zbMATH DE number 1078282 (Why is no real title available?)
• Embedding the diamond graph in L_p and dimension reduction in L₁
• Crossing edge minimization in radial outerplanar layered graphs using segment paths
• Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
• On triangulating \(k\)-outerplanar graphs
• Bandwidth and low dimensional embedding
• Embedding k-Outerplanar Graphs into l1
• \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees
• Clin d'oeil on L₁-embeddable planar graphs
• On the 2-sum embedding conjecture
• Bandwidth and low dimensional embedding

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4471340)