The embroidery problem

Esther M. Arkin; George W. Hart; Joondong Kim; Irina Kostitsyna; Joseph S.B. Mitchell; Girishkumar R. Sabhnani; Steven S. Skiena

The embroidery problem

Esther M. Arkin
, George W. Hart
, Joondong Kim
, Irina Kostitsyna
, Joseph S.B. Mitchell
, Girishkumar R. Sabhnani
, Steven S. Skiena

Stony Brook University

Research output: Contribution to conference › Paper › peer-review

2 Scopus citations

Abstract

We consider the problem of embroidering a design pattern, given by a graph G, using a single minimum length thread. We give an exact polynomial-time algorithm for the case that G is connected. If G has multiple connected components, then we show that the problem is NP-hard and give a polynomial-time 2-approximation algorithm. We also present results for special cases of the problem with various objective functions.

Original language	English
Pages	135-138
Number of pages	4
State	Published - 2008
Event	20th Annual Canadian Conference on Computational Geometry, CCCG 2008 - Montreal, QC, Canada Duration: Aug 13 2008 → Aug 15 2008

Conference

Conference	20th Annual Canadian Conference on Computational Geometry, CCCG 2008
Country/Territory	Canada
City	Montreal, QC
Period	08/13/08 → 08/15/08

Cite this

@conference{bf3638d0ddb24b2e91ad137c654ce10d,

title = "The embroidery problem",

abstract = "We consider the problem of embroidering a design pattern, given by a graph G, using a single minimum length thread. We give an exact polynomial-time algorithm for the case that G is connected. If G has multiple connected components, then we show that the problem is NP-hard and give a polynomial-time 2-approximation algorithm. We also present results for special cases of the problem with various objective functions.",

author = "Arkin, \{Esther M.\} and Hart, \{George W.\} and Joondong Kim and Irina Kostitsyna and Mitchell, \{Joseph S.B.\} and Sabhnani, \{Girishkumar R.\} and Skiena, \{Steven S.\}",

year = "2008",

language = "English",

pages = "135--138",

note = "20th Annual Canadian Conference on Computational Geometry, CCCG 2008 ; Conference date: 13-08-2008 Through 15-08-2008",

}

TY - CONF

T1 - The embroidery problem

AU - Arkin, Esther M.

AU - Hart, George W.

AU - Kim, Joondong

AU - Kostitsyna, Irina

AU - Mitchell, Joseph S.B.

AU - Sabhnani, Girishkumar R.

AU - Skiena, Steven S.

PY - 2008

Y1 - 2008

N2 - We consider the problem of embroidering a design pattern, given by a graph G, using a single minimum length thread. We give an exact polynomial-time algorithm for the case that G is connected. If G has multiple connected components, then we show that the problem is NP-hard and give a polynomial-time 2-approximation algorithm. We also present results for special cases of the problem with various objective functions.

AB - We consider the problem of embroidering a design pattern, given by a graph G, using a single minimum length thread. We give an exact polynomial-time algorithm for the case that G is connected. If G has multiple connected components, then we show that the problem is NP-hard and give a polynomial-time 2-approximation algorithm. We also present results for special cases of the problem with various objective functions.

UR - https://www.scopus.com/pages/publications/84893402695

M3 - Paper

AN - SCOPUS:84893402695

SP - 135

EP - 138

T2 - 20th Annual Canadian Conference on Computational Geometry, CCCG 2008

Y2 - 13 August 2008 through 15 August 2008

ER -

The embroidery problem

Abstract

Conference

Other files and links

Fingerprint

Cite this