Теория Задачи Инструменты Социум Интересно

Личный Кабинет

Войдите или зарегистрируйтесь
Лаборатория LMatrix
Лаборатория Lmatrix занимается оптимизацией транспортных задач. Сюда можно отнести задачи поиска кратчайшего пути в ориентированных графах, применимые как к масштабам города и страны, классическую задачу обхода (коммивояжера), задачи оптимизации доставки грузов, задачи трехмерной упаковки.
Новости проекта

31.05.2013 - Универсиада. Маршрут по России и Татарстану. Официально и математически.

Огонь Универсиады приближается к финишу в Казани, но прежде пройдет по 43 городам республики Татарстан. Все об маршрутах огня в нашем анонсе.

Тематические статьи

26.07.2013 - Монитор в автомобиле будет дублировать экран смартфона

Водители смогут увидеть точную копию экрана своего смартфона на мониторе бортовой системы автомобиля. О сотрудничестве в этом направлении договорились разработчик ПО для удаленного управления устройствами RealVNC и производитель процессоров Texas Instruments.

29.03.2013 - Facebook на днях анонсирует собственный смартфон на Android

На следующей неделе Facebook собирается представить собственный смартфон с кастомизированной версией Android, утверждают источники. Ранее глава компании Марк Цукерберг опровергал слухи о выпуске собственного смартфона.

29.03.2013 - Основатель Facebook М.Цукерберг создает политическую организацию

Основатель социальной сети Facebook Марк Цукерберг создает политическую организацию, которая займется такими вопросами, как реформа образования, иммиграция и научные исследования, передает Associated Press со ссылкой на анонимный источник.

Дэвид Эппштейн. Публикации. Часть Q-S

22 апреля 2011 года в 06:43   Просмотров: 4403

Quadrilateral meshing by circle packing

@inproceedings{BerEpp-CGC-97,
title = {{Quadrilateral meshing by circle packing}},
author = {Marshall Wayne Bern and David Eppstein},
eprint = {cs.CG/9908016},
booktitle = {Proc. 2nd CGC Worksh. Computational Geometry},
year = {1997}}

@inproceedings{BerEpp-IMR-97,
title = {{Quadrilateral meshing by circle packing}},
author = {Marshall Wayne Bern and David Eppstein},
eprint = {cs.CG/9908016},
booktitle = {Proc. 6th Int. Meshing Roundtable},
publisher = {Sandia Nat. Lab.},
pages = {7--20},
month = {October},
year = {1997},
url = {http://www.ics.uci.edu/~eppstein/pubs/BerEpp-MRT-97.pdf}}

@misc{cs.CG/9908016,
title = {{Quadrilateral meshing by circle packing}},
author = {Marshall Wayne Bern and David Eppstein},
eprint = {cs.CG/9908016},
howpublished = {ACM Computing Research Repository},
month = {August},
year = {1999}}

@article{BerEpp-IJCGA-00,
title = {{Quadrilateral meshing by circle packing}},
author = {Marshall Wayne Bern and David Eppstein},
eprint = {cs.CG/9908016},
journal = {Int. J. Computational Geometry {\&} Applications},
volume = {10},
number = {4},
pages = {347--360},
month = {August},
year = {2000},
review = {MR-2001f-52031}}

@article{MR-2001f-52031,
reviews = {BerEpp-IJCGA-00},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Quadrilateral meshing by circle packing}},
volume = {2001f},
number = {52031},
year = {2001}}

Quasiconvex analysis of backtracking algorithms

@misc{cs.DS/0304018,
title = {{Quasiconvex analysis of backtracking algorithms}},
author = {David Eppstein},
eprint = {cs.DS/0304018},
howpublished = {ACM Computing Research Repository},
month = {April},
year = {2003}}

@inproceedings{Epp-SODA-04-qaba,
title = {{Quasiconvex analysis of backtracking algorithms}},
author = {David Eppstein},
eprint = {cs.DS/0304018},
booktitle = {Proc. 15th Symp. Discrete Algorithms},
publisher = {ACM and SIAM},
pages = {781--790},
month = {January},
year = {2004}}

Quasiconvex programming

@incollection{Epp-MSRI-05,
title = {{Quasiconvex programming}},
author = {David Eppstein},
eprint = {cs.CG/0412046},
booktitle = {Combinatorial and Computational Geometry},
editor = {Jacob E. Goodman and J{\'a}nos Pach and Emo Welzl},
series = {MSRI Publications},
publisher = {Cambridge Univ. Press},
note = {To appear.}}

@misc{cs.CG/0412046,
title = {{Quasiconvex programming}},
author = {David Eppstein},
eprint = {cs.CG/0412046},
howpublished = {ACM Computing Research Repository},
month = {December},
year = {2004}}

Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions

@inproceedings{EppEri-SCG-98,
title = {{Raising roofs, crashing cycles, and playing pool: applications
of a data structure for finding pairwise interactions}},
author = {David Eppstein and Jeffrey Gordon Erickson},
booktitle = {Proc. 14th Symp. Computational Geometry},
publisher = {ACM},
pages = {58--67},
month = {June},
year = {1998},
review = {MR-2000i-68185}}

@article{MR-2000i-68185,
reviews = {EppEri-SCG-98},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Raising roofs, crashing cycles, and playing pool: applications
of a data structure for finding pairwise interactions}},
volume = {2000i},
number = {68185},
year = {2000}}

@article{EppEri-DCG-99,
title = {{Raising roofs, crashing cycles, and playing pool: applications
of a data structure for finding pairwise interactions}},
author = {David Eppstein and Jeffrey Gordon Erickson},
journal = {Discrete {\&} Computational Geometry},
volume = {22},
number = {4},
pages = {569--592},
year = {1999},
note = {Special issue for SCG 1998}}

Re: Geometry problem: Optimal direction. Known results?

@misc{Epp-smr-04,
title = {{Re: Geometry problem: Optimal direction. Known results?}},
author = {David Eppstein},
howpublished = {Message to sci.math.research bulletin board},
month = {21 May},
year = {2004},
url = {http://mathforum.org/epigone/sci.math.research/slexyaxsle}}

Reference caching using unit distance redundant codes for activity reduction on address buses

@inproceedings{EppGiv-ESCODES-02,
title = {{Reference caching using unit distance redundant codes for activity
reduction on address buses}},
author = {David Eppstein and Tony Digaleh Givargis},
booktitle = {Proc. Worksh. Embedded System Codesign (ESCODES '02)},
pages = {43--48},
month = {September},
year = {2002}}

Regression depth and center points

@misc{cs.CG/9809037,
title = {{Regression depth and center points}},
author = {Annamaria Beatrice Amenta and Marshall Wayne Bern and David Eppstein
and Shang-Hua Teng},
eprint = {cs.CG/9809037},
howpublished = {ACM Computing Research Repository},
month = {September},
year = {1998}}

@inproceedings{AmeBerEpp-CGC-98,
title = {{Regression depth and center points}},
author = {Annamaria Beatrice Amenta and Marshall Wayne Bern and David Eppstein
and Shang-Hua Teng},
eprint = {cs.CG/9809037},
booktitle = {Proc. 3rd CGC Worksh. Computational Geometry},
month = {October},
year = {1998},
url = {http://www.cs.brown.edu/cgc/cgc98/final/final9.pdf}}

@article{AmeBerEpp-DCG-00,
title = {{Regression depth and center points}},
author = {Annamaria Beatrice Amenta and Marshall Wayne Bern and David Eppstein
and Shang-Hua Teng},
eprint = {cs.CG/9809037},
journal = {Discrete {\&} Computational Geometry},
volume = {23},
number = {3},
pages = {305--323},
year = {2000},
url = {http://link.springer-ny.com/link/service/journals/00454/bibs/0023003/00230305.html},
review = {MR-2001e-52024}}

@article{MR-2001e-52024,
reviews = {AmeBerEpp-DCG-00},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Regression depth and center points}},
author = {P. Laurie Davies},
volume = {2001e},
number = {52024},
year = {2001},
text = {P. J. Rousseeuw and M. Hubert [Discrete Comput. Geom. 22 (1999),
no. 2, 167--176; MR 2000e:52024; J. Amer. Statist. Assoc. 94 (1999),
no. 446, 388--433; MR 2000i:62070] made the following two conjectures
concerning the regression depth of points in $d$-dimensional Euclidean
space: Conjecture 1. For any $d$-dimensional set of $n$ points there
exists a hyperplane having regression depth $\lceil\frac{n}{d+1}\rceil$.
Conjecture 2. For any point set there exist a partition into $\lceil
\frac{n}{d+1}\rceil$ subsets and a hyperplane that has nonzero regression
depth in each subset. The authors prove the first conjecture and make
some progress on the second. The problems arise in the context of robust
regression and have a natural geometric formulation. The proofs are based
on projective geometry and are consequently of a completely different
nature from the usual proofs of theorems in the area of robust statistics.
The authors also consider the computational aspects of the problems.}}

Representing all minimum spanning trees with applications to counting and generation

@techreport{Epp-TR-95-50,
title = {{Representing all minimum spanning trees with applications to
counting and generation}},
author = {David Eppstein},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {95-50},
year = {1995},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-95-50.pdf}}

Reset sequences for monotonic automata

@inproceedings{Epp-ICALP-88,
title = {{Reset sequences for monotonic automata}},
author = {David Eppstein},
booktitle = {Proc. 15th Int. Coll. Automata, Languages, and Programming
(ICALP 1988)},
number = {317},
editor = {Timo Lepist{\"o} and Arto Salomaa},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
pages = {230--238},
month = {July},
year = {1988}}

@article{Epp-SJC-90,
title = {{Reset sequences for monotonic automata}},
author = {David Eppstein},
journal = {SIAM J. Computing},
publisher = {SIAM},
volume = {19},
number = {3},
pages = {500--510},
month = {June},
year = {1990},
review = {MR-91f:68070}}

@article{MR-91f:68070,
reviews = {Epp-SJC-90},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Reset sequences for monotonic automata}},
author = {K. Vairavan},
number = {91f:68070},
year = {1991}}

Searching for spaceships

@misc{cs.AI/0004003,
title = {{Searching for spaceships}},
author = {David Eppstein},
eprint = {cs.AI/0004003},
howpublished = {ACM Computing Research Repository},
month = {April},
year = {2000}}

@incollection{Epp-MSRI-02,
title = {{Searching for spaceships}},
author = {David Eppstein},
eprint = {cs.AI/0004003},
booktitle = {More Games of No Chance},
number = {42},
editor = {Richard J. Nowakowski},
series = {MSRI Publications},
publisher = {Cambridge Univ. Press},
pages = {433--453},
year = {2002},
url = {http://www.msri.org/publications/books/Book42/files/eppstein.pdf},
review = {MR-2004b:91044}}

@article{MR-2004b:91044,
reviews = {Epp-MSRI-02},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Searching for spaceships}},
number = {2004b:91044},
year = {2004}}

Selected open problems in graph drawing

@inproceedings{BraEppGoo-GD-03,
title = {{Selected open problems in graph drawing}},
author = {Franz-Josef Brandenburg and David Eppstein and Michael T. Goodrich
and Stephen G. Kobourov and Giuseppe Liotta and Petra Mutzel},
booktitle = {Proc. 11th Int. Symp. Graph Drawing (GD 2003)},
number = {2912},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
pages = {515--539},
month = {September},
year = {2003}}

Separating geometric thickness from book thickness

@misc{math.CO/0109195,
title = {{Separating geometric thickness from book thickness}},
author = {David Eppstein},
eprint = {math.CO/0109195},
howpublished = {arXiv.org e-Print archive},
month = {September},
year = {2001}}

Separating thickness from geometric thickness

@inproceedings{Epp-GD-02,
title = {{Separating thickness from geometric thickness}},
author = {David Eppstein},
eprint = {math.CO/0204252},
booktitle = {Proc. 10th Int. Symp. Graph Drawing (GD 2002)},
number = {2528},
editor = {Michael T. Goodrich and Stephen G. Kobourov},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
pages = {150--161},
year = {2002}}

@misc{math.CO/0204252,
title = {{Separating thickness from geometric thickness}},
author = {David Eppstein},
eprint = {math.CO/0204252},
howpublished = {arXiv.org e-Print archive},
month = {April},
year = {2002}}

@incollection{Epp-TTGG-04,
title = {{Separating thickness from geometric thickness}},
author = {David Eppstein},
eprint = {math.CO/0204252},
booktitle = {Towards a Theory of Geometric Graphs},
number = {342},
editor = {J{\'a}nos Pach},
series = {Contemporary Mathematics},
publisher = {Amer. Math. Soc.},
pages = {75--86},
year = {2004}}

Separator based sparsification for dynamic planar graph algorithms

@inproceedings{EppGalIta-STOC-93,
title = {{Separator based sparsification for dynamic planar graph algorithms}},
author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Thomas
H. Spencer},
booktitle = {Proc. 25th Symp. Theory of Computing},
publisher = {ACM},
pages = {208--217},
month = {May},
year = {1993},
url = {http://www.acm.org/pubs/citations/proceedings/stoc/167088/p208-eppstein/}}

Separator based sparsification I: planarity testing and minimum spanning trees

@article{EppGalIta-JCSS-96,
title = {{Separator based sparsification I: planarity testing and minimum
spanning trees}},
author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Thomas
H. Spencer},
journal = {J. Computer {\&} Systems Sciences},
volume = {52},
number = {1},
pages = {3--27},
month = {February},
year = {1996},
url = {http://dx.doi.org/10.1006/jcss.1996.0002},
note = {Special issue for 25th STOC},
review = {MR-97c:05052}}

@article{MR-97c:05052,
reviews = {EppGalIta-JCSS-96},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Separator based sparsification I: planarity testing and minimum
spanning trees}},
author = {Fabrizio Luccio},
number = {97c:05052},
year = {1997},
text = {Based on the fundamental sparsification technique devised by Eppstein,
Galil, Italiano and Nissenzweig for the design of dynamic graph algorithms,
this paper shows how a planar graph can be efficiently processed under
the insertions and deletions of edges that preserve planarity. Although
the definition of planarity crucially relies on the concept of plane
embedding, the present technique is applied independently of the embedding,
which may be altered by the graph changes.

The major results are a fully dynamic planarity test working in $O(n^{1/2})$
amortized time per update or query, where $n$ is the number of vertices,
and various efficient dynamic algorithms to maintain connected components,
minimum spanning forests, and 2-edge-connected components, all valid
for planar graphs. As an overall comment, this is a significant and useful
addition to the algorithmic theory of planar graphs.}}

Separator based sparsification II: edge and vertex connectivity

@techreport{EppGalIta-TR-96-13,
title = {{Separator based sparsification II: edge and vertex connectivity}},
author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Thomas
H. Spencer},
address = {via Torino 155, 30173 Venezia Mestre, ITALY},
institution = {Univ. Ca' Foscari di Venezia, Dip. di Mathematica Applicata
ed Informatica},
pages = {CS96-13},
month = {October},
year = {1996}}

@article{EppGalIta-SJC-99,
title = {{Separator based sparsification II: edge and vertex connectivity}},
author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Thomas
H. Spencer},
journal = {SIAM J. Computing},
publisher = {SIAM},
volume = {28},
number = {1},
pages = {341--381},
year = {1999},
url = {http://dx.doi.org/10.1137/S0097539794269072},
review = {MR-99g:05058}}

@article{MR-99g:05058,
reviews = {EppGalIta-SJC-99},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Separator based sparsification II: edge and vertex connectivity}},
author = {Fabrizio Luccio},
number = {99g:05058},
year = {1999},
text = {A continuation of a series of basic contributions on dynamic graphs,
produced by the same authors [see Part I, J. Comput. System Sci. 52 (1996),
no. 1, 3--27; MR 97c:05052], this paper deals with the maintenance of
a planar graph under insertion and deletion of edges. The main results
are low-complexity amortized algorithms to retain information about vertex
connectivity. Although the definition of planarity relies on the existence
of a plane embedding, the authors devise techniques to keep the graph
planar under edge insertion without reference to any embedding (which
may in fact change).

This is another significant contribution to the important field of plane
graph algorithms, based on the concept of sparse certificate.}}

Sequence comparison with mixed convex and concave costs

@techreport{Epp-TR-88,
title = {{Sequence comparison with mixed convex and concave costs}},
author = {David Eppstein},
address = {New York, NY, 10027, USA},
institution = {Columbia Univ., Computer Science Dept.},
number = {CUCS-382-88},
year = {1988}}

@article{Epp-Algs-90,
title = {{Sequence comparison with mixed convex and concave costs}},
author = {David Eppstein},
journal = {J. Algorithms},
volume = {11},
number = {1},
pages = {85--101},
month = {March},
year = {1990},
review = {MR-91h:68031}}

@article{MR-91h:68031,
reviews = {Epp-Algs-90},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Sequence comparison with mixed convex and concave costs}},
number = {91h:68031},
year = {1991}}

Sets of points with many halving lines

@techreport{Epp-TR-92-86,
title = {{Sets of points with many halving lines}},
author = {David Eppstein},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {92-86},
year = {1992},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-92-86.pdf}}

Setting parameters by example

@misc{cs.DS/9907001,
title = {{Setting parameters by example}},
author = {David Eppstein},
eprint = {cs.DS/9907001},
howpublished = {ACM Computing Research Repository},
month = {July},
year = {1999}}

@inproceedings{Epp-FOCS-99,
title = {{Setting parameters by example}},
author = {David Eppstein},
eprint = {cs.DS/9907001},
booktitle = {Proc. 40th Symp. Foundations of Computer Science},
publisher = {IEEE},
pages = {309--318},
month = {October},
year = {1999}}

@article{Epp-SJC-03,
title = {{Setting parameters by example}},
author = {David Eppstein},
eprint = {cs.DS/9907001},
journal = {SIAM J. Computing},
publisher = {SIAM},
volume = {32},
number = {3},
pages = {643--653},
year = {2003},
url = {http://dx.doi.org/10.1137/S0097539700370084},
review = {MR-2004g:90114}}

@article{MR-2004g:90114,
reviews = {Epp-SJC-03},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Setting parameters by example}},
author = {Sheng Bau},
number = {2004g:90114},
year = {2004},
text = {If a parametric optimization problem and a desired optimal solution
are given, the parameter values that lead to the given problem and the
solution are to be sought. This is an "inverse parametric optimization"
problem. This paper describes algorithms for solving such problems for
minimum spanning trees, shortest paths and some other subgraph problems
and discusses applications in multicast routing, vehicle path planning,
resource allocation, and board game programming.}}

Shortest path along an MST

@misc{Epp-ct-99,
title = {{Shortest path along an MST}},
author = {David Eppstein},
howpublished = {Message to comp.theory bulletin board},
month = {April},
year = {1999},
url = {http://groups.google.com/groups?threadm=14098.38770.666234.83882@euclid.ics.uci.edu}}

Shortest paths in an arrangement with $k$ line orientations

@inproceedings{EppHar-SODA-99,
title = {{Shortest paths in an arrangement with $k$ line orientations}},
author = {David Eppstein and David Hart},
booktitle = {Proc. 10th Symp. Discrete Algorithms},
publisher = {ACM and SIAM},
pages = {310--316},
month = {January},
year = {1999}}

Simultaneous strong separations of probabilistic and unambiguous complexity classes

@article{EppHemTis-MST-92,
title = {{Simultaneous strong separations of probabilistic and unambiguous
complexity classes}},
author = {David Eppstein and Lane A. Hemachandra and James Tisdall and
B{\"u}lent Yener},
journal = {Mathematical Systems Theory},
volume = {25},
number = {1},
pages = {23--36},
year = {1992},
url = {http://www.ics.uci.edu/~eppstein/pubs/EppHemTis-MST-92.pdf},
review = {MR-92j:68031}}

@article{MR-92j:68031,
reviews = {EppHemTis-MST-92},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Simultaneous strong separations of probabilistic and unambiguous
complexity classes}},
author = {Marius Zimand},
number = {92j:68031},
year = {1992}}

Single-strip triangulation of manifolds with arbitrary topology

@inproceedings{GopEpp-EG-04,
title = {{Single-strip triangulation of manifolds with arbitrary topology}},
author = {Gopi Meenakshisundaram and David Eppstein},
eprint = {cs.CG/0405036},
booktitle = {Proc. 25th Conf. Eur. Assoc. for Computer Graphics (EuroGraphics
'04)},
pages = {371--379},
year = {2004},
note = {{\it Computer Graphics Forum}, vol. 23, no. 3.
Winner, second-best paper award.}}

@inproceedings{GopEpp-SCG-04,
title = {{Single-strip triangulation of manifolds with arbitrary topology}},
author = {Gopi Meenakshisundaram and David Eppstein},
eprint = {cs.CG/0405036},
booktitle = {Proc. 20th Symp. Computational Geometry},
publisher = {ACM},
pages = {455--456},
year = {2004},
note = {Abstract for video in 13th Video Review of Computational Geometry.}}

@misc{cs.CG/0405036,
title = {{Single-strip triangulation of manifolds with arbitrary topology}},
author = {Gopi Meenakshisundaram and David Eppstein},
eprint = {cs.CG/0405036},
howpublished = {ACM Computing Research Repository},
month = {May},
year = {2004}}

Skip-webs: efficient distributed data structures for multi-dimensional data sets

@inproceedings{ArgEppGoo-PODC-05,
title = {{Skip-webs: efficient distributed data structures for multi-dimensional
data sets}},
author = {Lars Arge and David Eppstein and Michael T. Goodrich},
eprint = {cs.DC/0507050},
booktitle = {Proc. 24th ACM SIGACT-SIGOPS Symp. Principles of Distributed
Computing (PODC 2005)},
note = {To appear.}}

@misc{cs.DC/0507050,
title = {{Skip-webs: efficient distributed data structures for multi-dimensional
data sets}},
author = {Lars Arge and David Eppstein and Michael T. Goodrich},
eprint = {cs.DC/0507050},
howpublished = {ACM Computing Research Repository},
month = {July},
year = {2005}}

Small maximal independent sets and faster exact graph coloring

@misc{cs.DS/0011009,
title = {{Small maximal independent sets and faster exact graph coloring}},
author = {David Eppstein},
eprint = {cs.DS/0011009},
howpublished = {ACM Computing Research Repository},
month = {November},
year = {2000}}

@inproceedings{Epp-WADS-01,
title = {{Small maximal independent sets and faster exact graph coloring}},
author = {David Eppstein},
eprint = {cs.DS/0011009},
booktitle = {Proc. 7th Worksh. Algorithms and Data Structures (WADS 2001)},
number = {2125},
editor = {Frank K. H. A. Dehne and J{\"o}rg-Rudiger Sack and Roberto Tamassia},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
pages = {462--470},
month = {August},
year = {2001},
review = {MR-2003j:05117}}

@article{MR-2003j:05117,
reviews = {Epp-WADS-01},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Small maximal independent sets and faster exact graph coloring}},
number = {2003j:05117},
year = {2003}}

@article{Epp-JGAA-03,
title = {{Small maximal independent sets and faster exact graph coloring}},
author = {David Eppstein},
eprint = {cs.DS/0011009},
journal = {J. Graph Algorithms {\&} Applications},
volume = {7},
number = {2},
pages = {131--140},
year = {2003},
note = {Special issue for WADS'01}}

Spanning trees and spanners

@techreport{Epp-TR-96-16,
title = {{Spanning trees and spanners}},
author = {David Eppstein},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {96-16},
year = {1996},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf}}

@incollection{Epp-HCG-00,
title = {{Spanning trees and spanners}},
author = {David Eppstein},
booktitle = {Handbook of Computational Geometry},
publisher = {Elsevier},
editor = {J{\"o}rg-Rudiger Sack and Jorge Urrutia},
pages = {425--461},
year = {2000},
chapter = {9}}

Sparse dynamic programming

@inproceedings{EppGalGia-SODA-90,
title = {{Sparse dynamic programming}},
author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
F. Italiano},
booktitle = {Proc. 1st Symp. Discrete Algorithms},
publisher = {ACM and SIAM},
pages = {513--522},
month = {January},
year = {1990}}

Sparse dynamic programming I: linear cost functions

@techreport{EppGalIta-TR-89-I,
title = {{Sparse dynamic programming I: linear cost functions}},
author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
F. Italiano},
address = {New York, NY, 10027, USA},
institution = {Columbia Univ., Computer Science Dept.},
number = {CUCS-471-89},
year = {1989}}

@article{EppGalGia-JACM-92-I,
title = {{Sparse dynamic programming I: linear cost functions}},
author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
F. Italiano},
journal = {J. ACM},
publisher = {ACM},
volume = {39},
number = {3},
pages = {519--545},
month = {July},
year = {1992},
url = {http://www.acm.org/pubs/citations/journals/jacm/1992-39-3/p519-eppstein/},
review = {MR-93i:90107a}}

@article{MR-93i:90107a,
reviews = {EppGalGia-JACM-92-I},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Sparse dynamic programming I: linear cost functions}},
author = {Moshe Sniedovich},
number = {93i:90107a},
year = {1993}}

Sparse dynamic programming II: convex and concave cost functions

@techreport{EppGalIta-TR-89-II,
title = {{Sparse dynamic programming II: convex and concave cost functions}},
author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
F. Italiano},
address = {New York, NY, 10027, USA},
institution = {Columbia Univ., Computer Science Dept.},
number = {CUCS-472-89},
year = {1989}}

@article{EppGalGia-JACM-92-II,
title = {{Sparse dynamic programming II: convex and concave cost functions}},
author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
F. Italiano},
journal = {J. ACM},
publisher = {ACM},
volume = {39},
number = {3},
pages = {546--567},
month = {July},
year = {1992},
url = {http://www.acm.org/pubs/citations/journals/jacm/1992-39-3/p546-eppstein/},
review = {MR-93i:90107b}}

@article{MR-93i:90107b,
reviews = {EppGalGia-JACM-92-II},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Sparse dynamic programming II: convex and concave cost functions}},
author = {Moshe Sniedovich},
number = {93i:90107b},
year = {1993}}

Sparsification --- A technique for speeding up dynamic graph algorithms
     
@inproceedings{EppGalIta-FOCS-92,
title = {{Sparsification --- A technique for speeding up dynamic graph algorithms}},
author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Amnon
Nissenzweig},
booktitle = {Proc. 33rd Symp. Foundations of Computer Science},
publisher = {IEEE},
pages = {60--69},
month = {October},
year = {1992}}

@techreport{EppGalIta-IBM-93,
title = {{Sparsification --- A technique for speeding up dynamic graph algorithms}},
author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Amnon
Nissenzweig},
address = {Rt. 134, Box 218, Yorktown Heights, NY, 10598, USA},
institution = {IBM, T. J. Watson Research Ctr.},
number = {RC 19272 (83907)},
year = {1993}}

@techreport{EppGalIta-TR-96-10,
title = {{Sparsification --- A technique for speeding up dynamic graph algorithms}},
author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Amnon
Nissenzweig},
address = {via Torino 155, 30173 Venezia Mestre, ITALY},
institution = {Univ. Ca' Foscari di Venezia, Dip. di Mathematica Applicata
ed Informatica},
number = {CS96-10},
month = {October},
year = {1996}}

@article{EppGalIta-JACM-97,
title = {{Sparsification --- A technique for speeding up dynamic graph algorithms}},
author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Amnon
Nissenzweig},
journal = {J. ACM},
publisher = {ACM},
volume = {44},
number = {5},
pages = {669--696},
month = {September},
year = {1997},
url = {http://doi.acm.org/10.1145/265910.265914},
review = {MR-98k:68039}}

@article{MR-98k:68039,
reviews = {EppGalIta-JACM-97},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Sparsification --- A technique for speeding up dynamic graph algorithms}},
author = {Peter B. Gibbons},
number = {98k:68039},
year = {1998},
text = {This paper makes a major contribution to the study of dynamic graph
algorithms that maintain some property of a changing graph more efficiently
than recomputation from scratch after each change. Dynamic algorithms
can be classified as fully dynamic, where both edge insertions and deletions
are allowed, or as partially dynamic where only insertions are allowed.
The improved performances for dynamic algorithms are achieved through
the use of the new technique of sparsification which, when applicable,
can speed up a $T(n,m)$ time bound for a graph $G$ with $n$ vertices
and $m$ edges to $T(n,O(n))$, almost the time needed if $G$ were sparse.
Sparsification involves partitioning the edges of $G$ into a collection
of $O(m/n)$ sparse subgraphs, each with $n$ vertices and $O(n)$ edges.
The information relevant for each subgraph can be summarised in an even
sparser subgraph, called a sparse certificate. Certificates are merged
in pairs, producing larger subgraphs which are made sparse again by computing
their certificates. The result is a balanced binary tree in which each
node is represented by a sparse certificate. Each update involves $\log
(m/n)$ graphs with $O(n)$ edges each, instead of one graph with $m$ edges.
A more careful partition into subgraphs causes each update to involve
a sequence of graphs with $O(n)$ edges in total. Three variants of the
sparsification technique are developed. The first is used in situations
where no previous fully dynamic algorithm was known and gives time bounds
of $O(n)$ per update. The second variant uses a dynamic data structure
to maintain certificates possessing a stability property, thereby transforming
time bounds of the form $O(m\sp p)$ into $O(n\sp p)$. In the third variant,
deletions are performed as in the first variant, and insertions by using
a partially dynamic algorithm. This leads to insertion times often matching
those of known partially dynamic algorithms, together with deletion times
similar to those of the first variant. Results include the maintenance
of minimum spanning forests, graph connectivity, graph 2-edge connectivity
and bipartiteness in time $O(n\sp {1/2})$ per change; 3-edge connectivity
in time $O(n\sp {2/3})$ per change; 4-edge connectivity in time $O(n\alpha(n))$
per change; $k$-edge connectivity for constant $k$ in time $O(n\log n)$
per change; 2-vertex connectivity and 3-vertex connectivity in time $O(n)$
per change; and 4-vertex connectivity in time $O(n\alpha(n))$ per change.
Further results speed up the insertion times to match the bounds of known
partially dynamic algorithms. The paper concludes with sections on recent
related work and remaining open questions.}}

Speeding up dynamic programming

@techreport{EppGalGia-TR-88,
title = {{Speeding up dynamic programming}},
author = {David Eppstein and Zvi Galil and Raffaele Giancarlo},
address = {New York, NY, 10027, USA},
institution = {Columbia Univ., Computer Science Dept.},
number = {CUCS-327-88},
year = {1988}}

@inproceedings{EppGalGia-FOCS-88,
title = {{Speeding up dynamic programming}},
author = {David Eppstein and Zvi Galil and Raffaele Giancarlo},
booktitle = {Proc. 29th Symp. Foundations of Computer Science},
publisher = {IEEE},
pages = {488--496},
month = {October},
year = {1988},
url = {http://www.ics.uci.edu/~eppstein/pubs/EppGalGia-FOCS-88.pdf}}

Subgraph isomorphism in planar graphs and related problems

@techreport{Epp-TR-94-25,
title = {{Subgraph isomorphism in planar graphs and related problems}},
author = {David Eppstein},
eprint = {cs.DS/9911003},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {94-25},
year = {1994},
url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-25.pdf}}

@inproceedings{Epp-SODA-95,
title = {{Subgraph isomorphism in planar graphs and related problems}},
author = {David Eppstein},
eprint = {cs.DS/9911003},
booktitle = {Proc. 6th Symp. Discrete Algorithms},
publisher = {ACM and SIAM},
pages = {632--640},
month = {January},
year = {1995},
review = {MR-95m:05178}}

@article{MR-95m:05178,
reviews = {Epp-SODA-95},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Subgraph isomorphism in planar graphs and related problems}},
number = {95m:05178},
year = {1995}}

@article{Epp-JGAA-99,
title = {{Subgraph isomorphism in planar graphs and related problems}},
author = {David Eppstein},
eprint = {cs.DS/9911003},
journal = {J. Graph Algorithms {\&} Applications},
volume = {3},
number = {3},
pages = {1--27},
year = {1999},
review = {MR-2001b-05154}}

@article{MR-2001b-05154,
reviews = {Epp-JGAA-99},
journal = {Mathematical Reviews},
publisher = {Amer. Math. Soc.},
title = {{Subgraph isomorphism in planar graphs and related problems}},
author = {Paul Klingsberg},
volume = {2001b},
number = {05154},
year = {2001},
text = {The subgraph isomorphism problem is the following. Given a graph
$G$ and another graph $H$, one must determine whether $G$ has a subgraph
that is isomorphic to $H$. In this fully general form, the problem is
NP-complete; but if $H$ is a fixed $l$-vertex graph, as the author points
out, this problem can clearly be solved in $O(n\sp l)$ time, where $n$
is the number of vertices of $G$. In the current paper, it is assumed
that $G$ and $H$ are planar; and in this case the author develops an
algorithm that requires only $O(C\sb Hn)$ time (although the constant
$C\sb H$ grows exponentially with $l$---necessarily so, if $\rm P\ne
NP$).

The main idea behind the algorithm is that of constructing a cover $\{G\sb
i\}$ for a planar graph $G$ and providing a so-called "tree decomposition"
for each element $G\sb i$ of the cover. (A tree decomposition of a graph
$G$ is a tree $T$ with these properties: (1) each node $N$ of $T$ is
provided with a label $L(N)\subseteq V(G)$; (2) for each $v\in V(G)$,
the set of tree nodes whose labels contain $v$ forms a contiguous subtree
of $T$; and (3) for each edge $\{v,w\}$ of $G$, there is at least one
node $N$ of $T$ such that both $v$ and $w$ are in $L(N)$.) Specifically,
for an $n$-vertex planar graph $G$, the author shows how, for any positive
integer $w$, to do the following in $O(w\sp 2n)$ time. He covers $G$
with a collection of subgraphs $\{G\sb i\}$, so that each vertex of $G$
is included in at most $w$ of the $\{G\sb i\}$; he provides for each
$G\sb i$ a tree decomposition in which all labels have $\le(3w-2)$ elements;
and he partitions $V(G)$ into subsets $\{S\sb i\}$ in such a way that,
for any connected $w$-vertex subgraph $H$ of $G$, if $i$ is the smallest
value for which $H\cap S\sb i$ is nonempty, then $H$ is a subgraph of
$G\sb i$ but is not a subgraph of $G\sb j$ for any $j>i$. The main result,
an algorithm for deciding the isomorphism question in linear time, is
then based on dynamic programming in the trees associated to the subgraphs
$\{G\sb i\}$.

The author also uses this technique to construct efficient algorithms
for a number of other decision and enumeration problems for planar graphs,
including connectivity, diameter, girth, induced subgraph isomorphism,
and shortest path.}}

@misc{cs.DS/9911003,
title = {{Subgraph isomorphism in planar graphs and related problems}},
author = {David Eppstein},
eprint = {cs.DS/9911003},
howpublished = {ACM Computing Research Repository},
month = {November},
year = {1999}}

Subquadratic nonobtuse triangulation of convex polygons

@techreport{Epp-TR-91-61,
title = {{Subquadratic nonobtuse triangulation of convex polygons}},
author = {David Eppstein},
address = {Irvine, CA, 92697-3425, USA},
institution = {Univ. of California, Irvine, Dept. of Information and Computer
Science},
number = {91-61},
year = {1991}}

Оставить комментарий

Пожалуйста, введите символы, показанные на рисунке.

Примеры решений задачи коммивояжера (TSP)
design by lmatrix
О проекте | Написать письмо | Ссылки | Литература | Карта сайта