Fakultät für Informatik
-
Technische Universität München
Lehrstuhl für Effiziente Algorithmen
Die bibliographische Datenbank LEABib
Suchen
•
Liste der Journale
•
Liste der Serien
•
Liste der Konferenzen
•
Ausgewählte Publikationen
Hilfe
Suche: Author="Nakano, Shin-ichi"
Als [
bib
] [
pdf
] [
ps
] [
dvi
] [
xml
] herunterladen.
A 4.31-approximation for the geometric unique coverage problem on unit disks
Takehiro Ito
,
Shin-ichi Nakano
,
Yoshio Okamoto
,
Yota Otachi
,
Ryuhei Uehara
,
Takeaki Uno
,
Yushi Uno
Theoretical Computer Science
544
, 2014, pp. 14-31
Efficient algorithms for a simple network design problem
Shin-ichi Nakano
,
Ryuhei Uehara
,
Takeaki Uno
Networks
62
(2), 2013, pp. 95-104
A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
Takehiro Ito
,
Shin-Ichi Nakano
,
Yoshio Okamoto
,
Yota Otachi
,
Ryuhei Uehara
,
Takeaki Uno
,
Yushi Uno
Lecture Notes in Computer Science
7357
, 2012, pp. 24-35
A 4.31-approximation for the geometric unique coverage problem on unit disks
Takehiro Ito
,
Shin-ichi Nakano
,
Yoshio Okamoto
,
Yota Otachi
,
Ryuhei Uehara
,
Takeaki Uno
,
Yushi Uno
Lecture Notes in Computer Science
7676
, 2012, pp. 372-381
Efficient enumeration of ordered trees with
k
leaves
Katsuhisa Yamanaka
,
Yota Otachi
,
Shin-ichi Nakano
Theoretical Computer Science
442
, 2012, pp. 22-27
Folding equilateral plane graphs
Zachary Abel
,
Erik D. Demaine
,
Martin L. Demaine
,
Sarah Eisenstat
,
Jayson Lynch
,
Tao B. Schardl
,
Isaac Shapiro-Ellowitz
Lecture Notes in Computer Science
7074
, 2011, pp. 574-583
Generating realistic roofs over a rectilinear polygon
Hee-Kap Ahn
,
Sang Won Bae
,
Christian Knauer
,
Mira Lee
,
Chan-Su Shin
,
Antoine Vigneron
Lecture Notes in Computer Science
7074
, 2011, pp. 60-69
Covering and piercing disks with two centers
Hee-Kap Ahn
,
Sang-Sub Kim
,
Christian Knauer
,
Lena Schlipf
,
Chan-Su Shin
,
Antoine Vigneron
Lecture Notes in Computer Science
7074
, 2011, pp. 50-59
Linear-time algorithms for hole-free rectilinear proportional contact graph representations
Muhammad Jawaherul Alam
,
Therese Biedl
,
Stefan Felsner
,
Andreas Gerasch
,
Michael Kaufmann
,
Stephen G. Kobourov
Lecture Notes in Computer Science
7074
, 2011, pp. 281-291
Range LCP
Amihood Amir
,
Alberto Apostolico
,
Gad M. Landau
,
Avivit Levy
,
Moshe Lewenstein
,
Ely Porat
Lecture Notes in Computer Science
7074
, 2011, pp. 683-692
Closest periodic vectors in
L_p
spaces
Amihood Amir
,
Estrella Eisenberg
,
Avivit Levy
,
Noa Lewenstein
Lecture Notes in Computer Science
7074
, 2011, pp. 714-723
Algorithm for single allocation problem on hub-and-spoke networks in 2-dimensional plane
Ryuta Ando
,
Tomomi Matsui
Lecture Notes in Computer Science
7074
, 2011, pp. 474-483
Simultaneous embedding of embedded planar graphs
Patrizio Angelini
,
Giuseppe Di Battista
,
Fabrizio Frati
Lecture Notes in Computer Science
7074
, 2011, pp. 271-280
External-memory multimaps
Elaine Angelino
,
Michael T. Goodrich
,
Michael Mitzenmacher
,
Justin Thaler
Lecture Notes in Computer Science
7074
, 2011, pp. 384-394
Semidefinite programming and approximation algorithms: A survey
Sanjeev Arora
Lecture Notes in Computer Science
7074
, 2011, pp. 6-9
On power-law distributed balls in bins and its applications to view size estimation
Ioannis Atsonios
,
Olivier Beaumont
,
Nicolas Hanusse
,
Yusik Kim
Lecture Notes in Computer Science
7074
, 2011, pp. 504-513
Verifying Nash equilibria in PageRank games on undirected web graphs
David Avis
,
Kazuo Iwama
,
Daichi Paku
Lecture Notes in Computer Science
7074
, 2011, pp. 415-424
Computing the visibility polygon using few variables
Luis Barba
,
Matias Korman
,
Stefan Langerman
,
Rodrigo I. Silveira
Lecture Notes in Computer Science
7074
, 2011, pp. 70-79
Parameterized complexity of the firefighter problem
Cristina Bazgan
,
Morgan Chopin
,
Michael R. Fellows
Lecture Notes in Computer Science
7074
, 2011, pp. 643-652
Finding contractions and induced minors in chordal graphs via disjoint paths
Rémy Belmonte
,
Petr A. Golovach
,
Pinar Heggernes
,
Pim van 't Hof
,
Marcin Kamiński
,
Daniël Paulusma
Lecture Notes in Computer Science
7074
, 2011, pp. 110-119
The School Bus Problem The School Bus Problem is an NP-hard vehicle routing problem in which the goal is to route buses that transport children to a school such that for each child, the distance travelled on the bus does not exceed the shortest distance from the child's home to the school by more than a given regret threshold. Subject to this constraint and bus capacity limit, the goal is to minimize the number of buses required. In this paper, we give a polynomial time 4-approximation algorithm when the children and school are located at vertices of a fixed tree. As a byproduct of our analysis, we show that the integrality gap of the natural set-cover formulation for this problem is also bounded by 4. We also present a constant approximation for the variant where we have a fixed number of buses to use, and the goal is to minimize the maximum regret.on trees
Adrian Bock
,
Elyot Grant
,
Jochen Könemann
,
Laura Sanità
Lecture Notes in Computer Science
7074
, 2011, pp. 10-19
Dominating induced matchings for
P_7
-free graphs in linear time
Andreas Brandstädt
,
Raffaele Mosca
Lecture Notes in Computer Science
7074
, 2011, pp. 100-109
Angle-restricted Steiner arborescences for flow map layout
Kevin Buchin
,
Bettina Speckmann
,
Kevin Verbeek
Lecture Notes in Computer Science
7074
, 2011, pp. 250-259
Two fixed-parameter algorithms for the cocoloring problem
Victor Campos
,
Sulamita Klein
,
Rudini Sampaio
,
Ana Silva
Lecture Notes in Computer Science
7074
, 2011, pp. 634-642
Explicit array-based compact data structures for triangulations
Luca Castelli Aleardi
,
Olivier Devillers
Lecture Notes in Computer Science
7074
, 2011, pp. 312-322
Seiten 1
2
3
4
5
6
7
>