Source author record

Yoshiko Wakabayashi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Decomposing highly edge-connected graphs into paths of any given length

In 2006, Barát and Thomassen posed the following conjecture: for each tree $T$ , there exists a natural number $k_T$ such that, if $G$ is a $k_T$ -edge-connected graph and $|E(G)|$ is divisible by $|E(T)|$ , then $G$ admits a decomposition into copies of $T$ . This conjecture was verified for stars, some bistars, paths of length $3$ , $5$ , and $2^r$ for every positive integer $r$ . We prove that this conjecture holds for paths of any fixed length.

preprint2015arXiv

Decompositions of highly connected graphs into paths of length five

We study the Decomposition Conjecture posed by Barát and Thomassen (2006), which states that for every tree $T$ there exists a natural number $k_T$ such that, if $G$ is a $k_T$ -edge-connected graph and $|E(T)|$ divides $|E(G)|$ , then $G$ admits a decomposition into copies of $T$ . In a series of papers, Thomassen verified this conjecture for stars, some bistars, paths of length $3$ , and paths whose length is a power of $2$ . We verify the Decomposition Conjecture for paths of length $5$ .

preprint2014arXiv

Polynomial-Time Approximation Schemes for Circle and Other Packing Problems

We give an asymptotic approximation scheme (APTAS) for the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augmented bins of height $1+γ$ , for some arbitrarily small number $γ> 0$ . Our algorithm is polynomial on $\log 1/γ$ , and thus $γ$ is part of the problem input. For the special case that $γ$ is constant, we give a (one dimensional) resource augmentation scheme, that is, we obtain a packing into bins of unit width and height $1+γ$ using no more than the number of bins in an optimal packing. Additionally, we obtain an APTAS for the circle strip packing problem, whose goal is to pack a set of circles into a strip of unit width and minimum height. These are the first approximation and resource augmentation schemes for these problems. Our algorithm is based on novel ideas of iteratively separating small and large items, and may be extended to a wide range of packing problems that satisfy certain conditions. These extensions comprise problems with different kinds of items, such as regular polygons, or with bins of different shapes, such as circles and spheres. As an example, we obtain APTAS's for the problems of packing d-dimensional spheres into hypercubes under the $L_p$ -norm.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.