Papers of Sándor Fekete

Disclaimer:

These papers are for personal academic use only. Most of the versions linked from here are preliminary (and sometimes very early and unpolished) versions.
Sometimes they date considerably before and therefore are quite different from the actual published versions. (See Jeff Erickson's copyright page if you want to know why.)
If you are interested in clean details, or plan to work on follow-up research, I suggest you:

look at the actual printed article, which is referenced in the publication data;
get in touch with me at: s.fekete AT tu-bs.de.

My coauthors (by name)

My coauthors (by number)

Some papers are available in gzipped Postcript format as well as PDF (which in some cases may have higher quality images).

You may need:

	Adobe Acrobat Reader - to view PDF files
	AFPL GhostScript - which converts PS files to PDF
	Ghostgum's GSView which is a Windows GUI for GhostScript.

Accepted
Submitted

Published by publication year:

2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992

indicates changes since April 1, 2009.

Accepted

S.P. Fekete, C. Schmidt, A.Wegener, H.Hellbrück, S.Fischer,
"Empowered by Wireless Communication: Distributed Methods for Self-Organizing Traffic Collectives."
To appear in ACM Transactions on Autonomous and Adaptive Systems.

S.P. Fekete, J.S.B. Mitchell, C. Schmidt.
"Minimum covering with travel cost".
To appear in 20th International Symposium on Algorithms and Computation (ISAAC 2009).

S.P. Fekete, C. Schmidt,
"Polygon exploration with time-discrete vision".
In Computational Geometry: Theory and Applications, 43 (2010), 148-168.

Submitted

Ioannis Chatzigiannakis, Shlomi Dolev, S.P. Fekete, Othon Michail, and Paul Spirakis
Not all fair probabilistic schedulers are equivalent.
Submitted to the 13th International Conference On Principle Of DIstributed Systems (OPODIS 2009)

S.P. Fekete, C. Gray. A. Kröller.
"Evacuation of rectilinear polygons".
Submitted for publication.

R. Connelly, E.D. Demaine, M.L. Demaine, S.P. Fekete, S. Langerman, J.S.B. Mitchell, A. Ribó, G. Rote.
"Locked and unlocked chains of planar shapes".
Submitted to Discrete and Computational Geometry, 2007.

2009

M.E. Bender, S.P. Fekete, T.Kamphans, N.Schweer,
"Maintaining Arrays of Contiguous Objects".
In 17th International Symposium on Fundamentals of Computation Theory (FCT 2009), Springer LNCS 5699, pp. 14-25.

E.D. Demaine, S.P. Fekete, G. Rote, N.Schweer, D. Schymura, M. Zelke.
"Integer point sets minimizing average L1 distance: What Is the Optimal Shape of a Town?"
In 21st Canadian Conference on Computational Geometry, 2009, 145-148.

A.Kröller, D.Pfisterer, S.P. Fekete, S.Fischer,
"Algorithms and simulation methods for topology-aware sensor networks."
In J. Lerner, D. Wagner, K.A. Zweig (eds.), Algorithmics, 380-400, 2009, Springer LNCS #5515.
BibTeX data

E.M. Arkin, S.P. Fekete, K. Islam, H. Meijer, J.S.B.Mitchell, Yurai Núñez-Rodríguez, David Rappaport, V.Polishchuk, Henry Xiao,
``Not being (super)thin or solid is hard: A study of grid Hamiltonicity.''
Computational Geometry: Theory and Applications, 42 (2009) 582-605.

S.P. Fekete, T.Kamphans, N.Schweer,
"Online square packing".
In Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009), pp. 302-314, Springer LNCS #5664.

A.Wegener, H.Hellbrück, S.Fischer, B. Hendriks, C. Schmidt, S.P. Fekete,
" Designing a Decentralized Traffic Information System - AutoNomos."
In KiVS 2009 , (Proceedings of the 16. GTI/GI - Fachtagung Kommunikation in verteilten Systemen). Springer Series "Informatik Aktuelle", pp. 309-315.

S.P. Fekete. D. Fey, M. Komann, A.Kröller, M. Reichenbach, C. Schmidt,
"Distributed vision with smart pixels".
In 26th Annual ACM Proceedings of the Symposium on Computational Geometry (SoCG 2009), pp. 257-266.

J.A.Brenner, S.P. Fekete, J.van der Veen,
"A minimization version of a directed subgraph homeomorphism problem"
In Mathematical Methods of Operations Research, 69(2) 2009: 281ff.

S.P. Fekete, C. Schmidt.
"Low-cost tours for nearsighted orthogonal watchmen with discrete vision".
EuroCG 2009 (Proceedings 25th European Workshop on Computational Geometry), 171-174.
BibTeX data

S.P. Fekete, T.Kamphans, N.Schweer,
"Online square packing".
EuroCG 2009 (Proceedings 25th European Workshop on Computational Geometry), 269-272.
BibTeX data

S.P. Fekete (ed.),
"Algorithmic Aspects of Wireless Sensor Networks", (Proceedings of the 4th International Workshop ALGOSENSORS 2008); Springer LNCS #5389.
BibTeX data

2008

S.P. Fekete, M. E. Lübbecke, H. Meijer,
"Minimizing the stabbing number of matchings, spanning trees, and triangulations."
Discrete and Computational Geometry, 40(4): 595-621 (2008)
BibTeX data

S.P. Fekete, Alon Efrat, Poornananda R. Gaddehosur, J.S.B.Mitchell, V.Polishchuk, J.Suomela,
"Improved Approximation Algorithms for Relay Placement."
Algorithms - ESA 2008, 356-367.
BibTeX data

C.Becker, T. Baumgartner, A.Kröller, D.Pfisterer, S.P. Fekete,
"FRONTS - Foundations of Adaptive Networked Societies of Tiny Artefacts."
In FGSN '08 (Proceedings of 7. GI/ITG KuVS Fachgespräch ``Drahtlose Sensornetze'')
BibTeX data

S.P. Fekete, J.van der Veen. A. Ahmadinia, D. Göhringer, M. Majer, J.Teich,
"Offline and online aspects of defragmenting the module layout of a partially reconfigurable device"
IEEE Transactions on VLSI, 16(9): 1210-1219 (2008)
BibTeX data

S.P. Fekete, T.Kamphans, N.Schweer, J.van der Veen. J. Angermaier, D.Koch, J.Teich.
"No-Break Dynamic Defragmentation of Reconfigurable Devices."
In Eighteenth International Conference on Field-Programmable Logic and Applications (FPL2008).
BibTeX data

S.Fischer, D.Pfisterer, S.P. Fekete, A.Kröller,
"WISEBED - Pan-European Wireless Sensor Network Testbeds".
In KuVS '08 (Proceedings of GI/ITG KuVS Fachgespräch ``Kommunikation und Verteilte Systeme'')
BibTeX data

S.P. Fekete, A.Hall, E.Köhler, A.Kröller, C. Schmidt,
"The Maximum Energy-Constrained Dynamic Flow Problem."
SWAT 2008, 114-126.
BibTeX data

M. Komann, A.Kröller, C. Schmidt, D. Fey, S.P. Fekete.
"Emergent algorithms for centroid and orientation detection in high-performance embedded cameras".
Computing Frontiers 2008, 221-230.
BibTeX data

M.E. Bender, D.P. Bunde, E.D. Demaine, S.P. Fekete, V.J. Leung, H. Meijer, C.A. Phillips,
"Communication-Aware Processor Allocation for Supercomputers: Finding Point Sets of Small Average Distance"
Algorithmica, 50(2): 279-298 (2008)
BibTeX data

E.D. Demaine, M.D. Demaine, S.P. Fekete, M. Ishaque, E. Rafalin, R.T. Schweller, D.L. Souvaine.
"Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues."
Natural Computing, 7(3): 347-370 (2008)
BibTeX data

S.P. Fekete. A.Kröller,
"Topology and Routing in Sensor Networks."
In ALGOSENSORS 2007, 6-15.
BibTeX data

2007

S.P. Fekete, J.van der Veen.
"PackLib²: An integrated library of multi-dimensional packing problems."
European Journal on Operational Research, 183 (3), 1131-1135. ("Special issue on cutting and packing").
BibTeX data

M.A. Bender, S.P. Fekete, A.Kröller, J.S.B.Mitchell, V.Liberatore, V.Polishchuk, J.Suomela,
"The minimum-backlog problem."
MACIS 2007, (Mathematical Aspects of Computer and Information Sciences), 1-18.
BibTeX data

A.Wegener, H.Hellbrück, S.Fischer, C. Schmidt, S.P. Fekete,
"AutoCast: An adaptive data dissemination protocol for traffic information systems."
In 66th Semi-Annual IEEE Vehicular Technology Conference (VTC 2007-Fall) , 1947-1951.
BibTeX data

K. Buchin, M. Buchin, E.D. Demaine, M.L. Demaine, S.P. Fekete, D. El-Khechen, C. Knauer, A. Schulz, P. Taslakian.
"On Rolling Cube Puzzles".
19th Canadian Conference on Computational Geometry, 141-144, 2007.
BibTeX data

S.P. Fekete, J.Schepers, J.van der Veen.
"An exact algorithm for higher-dimensional orthogonal packing."
In Operations Research, Vol. 55, No. 3, 2007, pp. 569-587.
BibTeX data

E.D. Demaine, M.D. Demaine, S.P. Fekete, M. Ishaque, E. Rafalin, R.T. Schweller, D.L. Souvaine.
"Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues."
13th International Meeting on DNA Computing (DNA13), 1-14, 2007.
BibTeX data

J. Angermaier, D. Goehringer, M. Majer, J.Teich, S.P. Fekete, J.van der Veen.
"The Erlangen Slot Machine - A Platform for Interdisciplinary Research in Reconfigurable Computing"
In IT - Information Technology, Vol. 49, No. 3, 2007, pp. 143-148.
BibTeX data

A. Ahmadinia, C.Bobda, S.P. Fekete, J.Teich, J.van der Veen.
"Optimal free-space management and routing-conscious dynamic placement for reconfigurable computing."
IEEE Transactions on Computing, Vol. 56, No. 5, 2007, pp. 673-680.
BibTeX data

C.Buschmann, H.Hellbrück, S.Fischer, A.Kröller, S.P. Fekete.
"Radio propagation-aware distance estimation based on neighborhood comparison."
In European Workshop on Sensor Networks (EWSN 2007), 325-340.
BibTeX data

S.P. Fekete, C. Schmidt,
"Polygon exploration with discrete vision".
In 23rd European Workshop on Computational Geometry, 86-89.
BibTeX data

S.P. Fekete, J.van der Veen. J. Angermaier, M. Majer, D. Goehringer, J.Teich,
"Scheduling and communication-aware mapping of HW-SW modules for dynamically and partially reconfigurable SoC architectures"
In Architecture of Computing Systems (ARCS 2007), pp. 151-160.
BibTeX data

2006

S.P. Fekete, E.Köhler, J.Teich.
"Higher-dimensional packing with order constraints."
In SIAM Journal on Discrete Mathematics, Vol. 20, No. 4, 2006, pp. 1056-1078.
BibTeX data

S.P. Fekete, C. Schmidt, A.Wegener, S.Fischer.
"Hovering Data Clouds for recognizing traffic jams."
2nd International Symposium on Leveraging Applications of Formal Methods, Verification and Validation (IEEE-ISOLA 2006), 213-218.
BibTeX data

S.P. Fekete, A.Kröller, C.Buschmann, S.Fischer,
"Geometric Distance Estimation for Sensor Networks and Unit Disk Graphs."
In Proceedings of the Sixteenth Fall Workshop on Computational Geometry, 2006.
BibTeX data

S.P. Fekete, A.Kröller, D.Pfisterer, S.Fischer,
"Algorithmic aspects of large sensor networks."
Invited paper, in Proceedings of Mobility and Scalability in Wireless Sensor Networks (MSWSN 2006), 141-152.
BibTeX data

S.P. Fekete, J.van der Veen. M.Majer, J.Teich.
"Minimizing communication cost for reconfigurable slot modules."
In Sixteenth International Conference on Field-Programmable Logic and Applications (FPL2006), 535-540.
BibTeX data

J.A.Brenner, J.van der Veen, S.P. Fekete, J.de Oliveira Filho, W.Rosenstiel.
"Time-optimal routing-aware mapping to processor-like reconfigurable architectures."
In Sixteenth International Conference on Field-Programmable Logic and Applications (FPL2006), 527-534.
BibTeX data

C.Buschmann, H.Hellbrück, S.Fischer. S.P. Fekete, A.Kröller,
"Estimating distances using neighborhood intersection."
11th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA 2006).
BibTeX data

A.Wegener, E.Schiller, H.Hellbrück, S.P. Fekete, S.Fischer.
"Hovering Data Clouds: Decentralized and self-organizing information systems."
International Workshop on Self-Organizing Systems (IWSOS 2006), 243-247.
BibTeX data

E.D. Demaine, S.P. Fekete, S. Gal.
"Online searching with turn cost."
Theoretical Computer Science, 361 (2006), pp. 342-355.
BibTeX data

E.M. Arkin, M.A. Bender, S.P. Fekete, J.S.B.Mitchell, M. Skutella.
``The Freeze-Tag Problem: How to wake up a swarm of robots.'',
Algorithmica, 46 (2006), pp. 193-221
BibTeX data

J.A.Brenner, S.P. Fekete, J.van der Veen,
"Simultaneous Scheduling, Binding and Routing for Coarse-Grain Reconfigurable Architectures"
Electronic Notes in Discrete Mathematics, 25 (2006), 21-22.
BibTeX data

S.P. Fekete, A.Kröller,
"Geometry-Based Reasoning for a Large Sensor Network." (Video, 70 MB)
Accompanying two-page abstract, in
Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, 2006, 475-476.
BibTeX data

R. Connelly, E.D. Demaine, M.L. Demaine, S.P. Fekete, S. Langerman, J.S.B. Mitchell, A. Ribó, G. Rote.
"Locked and unlocked chains of planar shapes".
Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, 61-70, 2006.
BibTeX data

H. Alt, E.M. Arkin, H. Brönnimann, J. Erickson. S.P. Fekete, C. Knauer, J. Lenchner, J.S.B. Mitchell, K. Whittlesey.
"Minimum-Cost Coverage of Point Sets by Disks"
Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, 449-458, 2006.
BibTeX data

S.P. Fekete, R.Klein, A.N�chter.
"Online searching with an autonomous robot."
Full resolution (gzipped postscript, 2.2MB)
Computational Geometry: Theory and Applications, 34 (2), 2006, pp. 102-115
BibTeX data

A.Kröller, S.P. Fekete, D.Pfisterer, S.Fischer,
"Deterministic boundary recognition and topology extraction for large sensor networks"
Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 1000-1009.
BibTeX data

2005

E.M. Arkin, M.A. Bender, E.D. Demaine, S.P. Fekete, J.S.B.Mitchell, S. Sethia.
"Optimal covering tours with turn costs."
SIAM Journal on Computing, 35 (2005), 531-566.
BibTeX data

C.Bobda, A. Ahmadinia, M.Majer, J.Teich, S.P. Fekete, J.van der Veen.
"DyNoC: A Dynamic Infrastructure for Communication in Dynamically Reconfigurable Devices"
In 15th International Conference on Field-Programmable Logic and Applications (FPL 2005), 153-158.
BibTeX data

M.E. Bender, D.P. Bunde, E.D. Demaine, S.P. Fekete, V.J. Leung, H. Meijer, C.A. Phillips,
"Communication-Aware Processor Allocation for Supercomputers."
Workshop on Algorithms and Data Structures (WADS), 2005, Springer LNCS #3608, 169-181.
BibTeX data

S.P. Fekete, Michael Kaufmann, A.Kröller, Katharina Lehmann,
"A new approach for boundary recognition in geometric sensor networks"
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005, pp 82-85.
BibTeX data

C.Bobda, M.Majer, A. Ahmadinia, T. Haller, A. Linarth, J.Teich, S.P. Fekete, J.van der Veen.
"The Erlangen Slot Machine: A highly flexible FPGA-based reconfigurable platform"
In IEEE Symposium on Field-Programmable Custom Computing Machine (FPCCM 2005), 319-320.
BibTeX data

H. Alt, E.M. Arkin, H. Brönnimann, J. Erickson. S.P. Fekete, C. Knauer, J. Lenchner, J.S.B. Mitchell, S. Whitesides, K. Whittlesey.
"How to water carrots: geometric coverage problems for point sets"
Proc. 15th Annual Workshop on Computational Geometry and Vizualization, 2005, pp. 71-72.
BibTeX data

J.van der Veen. S.P. Fekete, M. Majer, A. Ahmadinia, C.Bobda, F. Hannig, J.Teich,
"Defragmenting the module layout of a partially reconfigurable device"
In Proc. 2005 International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA), as a "Distinguished Paper", pp. 92-101, 2005.
BibTeX data

A. Ahmadinia, C.Bobda, J.Ding, M.Majer, J.Teich, S.P. Fekete, J.van der Veen.
"A practical approach for circuit routing on dynamic reconfigurable devices"
In International Workshop on Rapid System Prototyping, (RSP 2005), 2005, 84-90.
BibTeX data

S.P. Fekete, R.Klein, A.N�chter.
"Online searching with an autonomous robot."
In In: M. Erdmann, D. Hsu, M. Overmars, A.F. v.d.Stappen, (eds.)
Algorithmic Foundations of Robotics VI. Springer-Verlag, 2005.
BibTeX data

A.Kröller, D.Pfisterer, C.Buschmann. S.P. Fekete, S.Fischer,
"Shawn: A new approach to simulating wireless sensor networks"
In: Design, Analysis, and Simulation of Distributed Systems, 2005, 117-124.
BibTeX data

S.P. Fekete, J.S.B.Mitchell, K.Beurer.
"On the continuous Fermat-Weber problem."
Operations Research, 53 (2005), 61-76.
BibTeX data

A.Kröller, S.P. Fekete, C.Buschmann. S.Fischer, D.Pfisterer,
"Koordinatenfreies Lokationsbewusstsein"
Information Technology, 47 (2), 2005, 70-78.
BibTeX data

C.Buschmann. D.Pfisterer, S.Fischer, S.P. Fekete, A.Kröller,
SpyGlass: A wireless sensor network visualizer
SIGBED Review, Volume 2, Number 1, January 2005, 1-6.
(Special Issue: Best of ACM SenSys 2004 Work-in-Progress)
BibTeX data

S.P. Fekete, H. Meijer,
"The one-round Voronoi game replayed"
Computational Geometry: Theory and Applications, 30 (2005), 81-94.
BibTeX data

2004

S.P. Fekete, J. Schepers.
"A general framework for bounds for higher-dimensional orthogonal packing problems."
Mathematical Methods of Operations Research, 60 (2004), 311-329.
BibTeX data

C.Buschmann. D.Pfisterer, S.Fischer, S.P. Fekete, A.Kröller,
SpyGlass: Taking a closer look into sensor networks
Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (ACM SenSys 2004), 301-302.
BibTeX data

A. Ahmadinia, C.Bobda, S.P. Fekete, J.Teich, J.van der Veen.
"Optimal routing-conscious dynamic placement for reconfigurable computing"
14th International Conference on Field-Programmable Logic and Application (FPL 2004),
Springer Lecture Notes in Computer Science, vol.3203, 2004, pp. 847-851.
BibTeX data

S.P. Fekete, R.Klein, A.N�chter.
"Online searching with an autonomous robot."
In Workshop on Algorithmic Foundations of Robotics, 2004, 335-350.
BibTeX data

S.P. Fekete, A.Kröller, D.Pfisterer, S.Fischer, C.Buschmann.
"Neighborhood-based topology recognition in sensor networks"
In ALGOSENSORS 2004.
Springer Lecture Notes in Computer Science, vol.3121, 2004, pp. 123-136.
BibTeX data

S.P. Fekete, R.Klein, A.N�chter.
"Searching with an autonomous robot." (Video, 150-250 MB)
Accompanying two-page abstract.
20th Annual ACM Symposium on Computational Geometry, 449-450, 2004.
BibTeX data

S.P. Fekete, J.Schepers.
"A combinatorial characterization of higher-dimensional orthogonal packing."
Mathematics of Operations Research, 29 (2004), pp. 353-368.
BibTeX data

S.P. Fekete, R. Fleischer, Aviezri Fraenkel, M. Schmitt.
"Traveling salesmen in the presence of competition."
Theoretical Computer Science, 313 (2004), pp. 377-392.
BibTeX data

S.P. Fekete, M. E. L�bbecke, H. Meijer,
"Minimizing the stabbing number of matchings, spanning trees, and triangulations."
Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 430-439.
BibTeX data

C.M. Bender, M.A. Bender, E.D. Demaine, S.P. Fekete.
"What is the optimal shape of a city?"
Journal of Physics A: Mathematical and General 37 (2004), pp. 147-159.
BibTeX data

2003

S.P. Fekete, H. Meijer,
"Maximum dispersion and geometric maximum weight cliques."
Algorithmica, 38 (3) (2003), pp. 501-511.
BibTeX data

S.P. Fekete, R.T. Firla, B. Spille.
"Characterizing matching as the intersection of matroids."
Mathematical Methods of Operations Research. 58 (2003), pp. 319-329.
BibTeX data

S.P. Fekete, M. Skutella. G. J. Woeginger,
"The complexity of economic equilibria for house allocation markets."
Information Processing Letters 88 (2003), pp. 219-223.
BibTeX data

A. Barvinok, S.P. Fekete, D.S. Johnson, A. Tamir, G. J. Woeginger, Russ Woodroofe.
"The geometric Maximum Traveling Salesman Problem."
Journal of the ACM, 50 (2003), 641-664.
BibTeX data

S.P. Fekete, H. Meijer,
"The one-round Voronoi game replayed"
Workshop on Algorithms and Data Structues.
Springer Lecture Notes in Computer Science, vol.2748, 2003, pp. 150-161.
BibTeX data

T.-R. Hsiang, E.M. Arkin, M.A. Bender, S.P. Fekete, J.S.B.Mitchell,
"Algorithms for rapidly dispersing robot swarms in unknown environments."
In: J.-D. Boissonnat, J. Burdick, K. Goldberg, S. Hutchinson, (eds.)
Algorithmic Foundations of Robotics V. Springer-Verlag, 2003, pp. 77-94.
BibTeX data

E.M. Arkin, S.P. Fekete, F. Hurtado, J.S.B.Mitchell, M. Noy, V. Sacristan, S. Sethia.
"On the reflexivity of point sets." (Full version, 28 pages)
Short version (17 pages) in: B. Aronov, S. Basu, J. Pach, and M. Sharir (eds.):
Discrete and Computational Geometry - The Goodman-Pollack Festschrift.
Series "Algorithms and Combinatorics", vol. 25, Springer-Verlag 2003, pp. 139--156.
BibTeX data

T.-R. Hsiang, E.M. Arkin, M.A. Bender, S.P. Fekete, J.S.B.Mitchell,
"Online Dispersion Algorithms for Swarms of Robots." (Video)
Accompanying two-page abstract
20th Annual ACM Proceedings of the Symposium on Computational Geometry, 382-383, 2003.
BibTeX data

S.P. Fekete, H. Meijer,
"The one-round Voronoi game replayed" (Extended Abstract)
19th European Conference on Computational Geometry. 2003, 15-18.
BibTeX data

E.M. Arkin, S.P. Fekete, J.S.B.Mitchell,
``An algorithmic study of manufacturing paperclips and other folded structures'',
Computational Geometry: Theory and Applications. 25 (2003), 117-138.
BibTeX data

2002

S.P. Fekete, H. Meijer, A. Rohe, W. Tietze.
"Solving a ``hard'' problem to approximate and ``easy'' one:
good and fast heuristics for large geometric maximum matching and maximum Traveling Salesman problems."
Journal of Experimental Algorithms. 7 (2002), article 11.
BibTeX data

E.M. Arkin, M.A. Bender, S.P. Fekete, J.S.B.Mitchell, M. Skutella.
``The Freeze-Tag Problem: how to wake up a swarm of robots'',
Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pp. 568-577.
BibTeX data

2001

M.Eiglsperger, S.P. Fekete, G. Klau.
"Orthogonal graph drawing."
In: M. Kaufmann, D. Wagner, eds.,
Drawing Graphs -- Models and Methods,
Springer Lecture Notes in Computer Science, vol. 2025, 2001, pp. 121-171,
BibTeX data

S.P. Fekete, R.T. Firla, B. Spille.
"Matching as the intersection of matroids."
Electronic Notes in Discrete Mathematics, vol. 10 (special issue for Euroconference on Combinatorics, Graph Theory and Applications), Elsevier Science 2001.
BibTeX data

S.P. Fekete, J.S.B.Mitchell,
"Terrain decomposition and layered manufacturing."
International Journal of Computational Geometry & Applications, 11 (6), 2001, pp. 647-668.
BibTeX data

S.P. Fekete, J.Schepers.
"New classes of lower bounds for the bin packing problem."
Mathematical Programming, 91 (2001), pp. 11-31.
BibTeX data

S.P. Fekete, H. Meijer, A. Rohe, W. Tietze.
"Solving a ``hard'' problem to approximate and ``easy'' one:
good and fast heuristics for large geometric maximum matching and maximum Traveling Salesman problems."
Proceedings Third International Workshop on Algorithm Engineering and Experiments (ALENEX'01),
Springer Lecture Notes in Computer Science, vol.2153, 2001, pp. 1-16.
BibTeX data

S.P. Fekete, E.K�hler, J.Teich.
"Multi-dimensional packing with order constraints."
Proc. 7th International Workshop on Algorithms and Data Structures
Springer Lecture Notes in Computer Science, vol. 2125, 2001, pp. 300-312.
BibTeX data

E.M. Arkin, S.P. Fekete, F. Hurtado, J.S.B.Mitchell, M. Noy, V. Sacristan, S. Sethia.
"On the reflexivity of point sets."
Proc. 7th International Workshop on Algorithms and Data Structures
Springer Lecture Notes in Computer Science, vol. 2125, 2001, pp. 192-204.
BibTeX data

S.P. Fekete, E.K�hler, J.Teich.
"Extending partial suborders."
Electronic Notes in Discrete Mathematics, vol. 8, (special issue for the Cologne-Twente Workshop on Graphs and Combinatorial Optimization), Elsevier Science, 2001.
BibTeX data

E.M. Arkin, M.A. Bender, S.P. Fekete, J.S.B.Mitchell, M. Skutella, M.O. Sztainberg.
"The freeze-tag problem: theoretical and experimental investigations."
11th Fall Workshop on Computational Geometry, 2001.
BibTeX data

S.P. Fekete, E.K�hler, J.Teich.
"Optimal FPGA module placement in space and time."
Proc. DATE 2001, Design, Automation and Test in Europe,
2001, pp. 658-665.
BibTeX data

J.Teich, S.P. Fekete, J.Schepers.
"Optimal hardware reconfiguration techniques."
Journal of Supercomputing, 19 (2001), pp. 57-75.
BibTeX data

C. Baur, S.P. Fekete
"Approximation of geometric dispersion problems."
Algorithmica, 30 (2001), pp. 451-470.
BibTeX data

E.J.Anderson, S.P. Fekete.
"Two-dimensional rendezvous search."
Operations Research, 49 (2001), pp. 107-118.
BibTeX data

S.P. Fekete, J.Kremer.
"Tree spanners in planar graphs."
Discrete Applied Mathematics, 108 (2001), pp. 85-103.
BibTeX data

E.M. Arkin, S.P. Fekete, J.S.B.Mitchell, S. Skiena.
"On the manufacturability of paperclips and sheet metal structures."
17th European Workshop on Computational Geometry 2001, pp. 187-190.
BibTeX data

E.M. Arkin, M.A. Bender, E.D. Demaine, S.P. Fekete, J.S.B.Mitchell, S. Sethia.
"Optimal covering tours with turn costs."
Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 01), pp. 138-147.
BibTeX data

2000

E.M. Arkin, S.P. Fekete, J.S.B.Mitchell,
"Approximation algorithms for lawn mowing and milling."
Computational Geometry: Theory and Applications. 17 (2000), pp. 25-50.
BibTeX data

E.M. Arkin, S.P. Fekete, F. Hurtado, J.S.B.Mitchell, M. Noy, V. Sacristan, S. Sethia.
"On the reflexivity of point sets."
Tenth Annual Fall Workshop On Computational Geometry, Stony Brook, NY, 2000.
BibTeX data

S.P. Fekete, J.S.B.Mitchell, K.Weinbrecht.
"On the continuous Weber and k-median problems."
Proceedings of the 16th Annual ACM Symposium on Computational Geometry, 2000, pp. 70-79.
BibTeX data

S.P. Fekete, H. Meijer,
"Maximum dispersion and geometric maximum weight cliques."
Proceedings Approximation Algorithms for Combinatorial Optimization, 2000, pp. 132-143.
BibTeX data

S.P. Fekete, H. Meijer,
"On minimum stars and maximum matchings."
Discrete and Computational Geometry, 2000, pp. 389-407.
BibTeX data

S.P. Fekete
"On simple polygonalizations with optimal area."
Discrete and Computational Geometry, 23 (2000), pp. 73-110.
BibTeX data

1999

J.Teich, S.P. Fekete, J.Schepers.
"Compile-time optimization of dynamic hardware reconfigurations."
Parallel and Distributed Processing Techniques and Applications (PDPTA'99), 1999, pp. 1097-1103.
BibTeX data

S.P. Fekete, H. Meijer,
"On minimum stars, minimum Steiner stars, and maximum matchings."
Proceedings of the 15th Annual ACM Symposium on Computational Geometry, 1999, pp. 217-226.
BibTeX data

S.P. Fekete.
"Simplicity and hardness of the Maximum Traveling Salesman Problem under geometric distances."
Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 99), 1999, pp. 337-345.
BibTeX data

S.P. Fekete, W.Hochst�ttler, S.Kromberg, C.Moll.
"The complexity of an inverse shortest path problem."
In: R. Graham, J. Kratochvil, J. Nesetril, F. Roberts, eds., Contemporary Trends Discrete Mathematics,
vol. 49, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, 1999, pp. 113-127.
BibTeX data

S.P. Fekete, H. Meijer,
"Rectangle and box visibility graphs in 3D."
International Journal of Computational Geometry and its Applications. 9 (1999), pp. 1-27.
BibTeX data

1998

S.P. Fekete, J.Kremer.
"Tree spanners in planar graphs."
24th International Annual Workshop on Graph-Theoretic Concepts in Computer Science (WG 98).
Springer Lecture Notes in Computer Science, vol. 1517, 1998, pp. 298-309.
BibTeX data

U. Faigle, S.P. Fekete, W.Hochst�ttler, W.Kern.
"The nukleon of cooperative games and an algorithm for matching games."
Mathematical Programming, 83 (1998), pp. 195-211.
BibTeX data

S.P. Fekete, W.R. Pulleyblank.
"Traveling the boundary of Minkowski sums."
Information Processing Letters, 66 (1998), pp. 171-174.
BibTeX data

C. Baur, S.P. Fekete
"Approximation of geometric dispersion problems."
Approximation Algorithms for Combinatorial Optimization (APPROX 98)
Springer Lecture Notes in Computer Science, vol. 1444, 1998, pp. 63-75.
BibTeX data

S.P. Fekete, J. Schepers,
"New classes of lower bounds for the bin packing problem."
Integer Programming and Combinatorial Optimization (IPCO 98), vol. 1412, 1998, pp. 257-270.
BibTeX data

E.J. Anderson, S.P. Fekete.
"Asymmetric rendezvous on the plane."
Proceedings of the 14th Annual ACM Symposium on Computational Geometry, 1998, pp. 365-373.
BibTeX data

P. Bose, H. Everett, S.P. Fekete, M. Houle, A. Lubiw, H. Meijer, K. Romanik, G. Rote, T. Shermer, S. Whitesides, C. Zelle.
"A visibility representation for graphs in three dimensions."
Journal of Graph Algorithms and Applications, 2 (3) (1998).
BibTeX data

U. Faigle, S.P. Fekete, W.Hochst�ttler, W.Kern.
"On approximately fair cost allocation for the Euclidean Traveling Salesman Problem."
OR Spektrum 20 (1998), pp. 29-37.
BibTeX data

S.P. Fekete, M. Houle, S. Whitesides.
"The wobbly logic engine: proving hardness of non-rigid graph representation problems."
Graph Drawing 97,
Springer Lecture Notes in Computer Science, vol. 1353, 1998, pp. 272-283.
BibTeX data

1997

S.P. Fekete, S.Khuller, M.Klemmstein, B.Raghavachari, N.Young.
"A network flow technique for finding low-weight bounded-degree trees."
Journal of Algorithms, 24 (1997), pp. 310-324.
BibTeX data

S.P. Fekete, J. Schepers.
"A new exact algorithm for general orthogonal d-dimensional knapsack problems."
Algorithms - ESA '97,
Springer Lecture Notes in Computer Science, vol. 1284, 1997, pp. 144-156.
BibTeX data

U. Faigle, S.P. Fekete, W.Hochst�ttler, W.Kern.
"On the complexity of testing membership in the core of min-cost spanning tree games."
International Journal of Game Theory, 26 (1997), pp. 361-366.
BibTeX data

S.P. Fekete, G. J. Woeginger.
"Angle-restricted tours in the plane."
Computational Geometry: Theory and Applications. 8 (1997), pp. 195-218.
BibTeX data

Achim Bachem, S.P. Fekete, B. Knab, R. Schrader, I. Vannahme, I. Weber, R. Wegener, K. Weinbrecht, B. Wichern.
"Analyse gro�er Datenmengen und Clusteralgorithmen im Bausparwesen."
In: C. Hipp, Geld, Finanzwirtschaft, Banken und Versicherungen, VVW Karlsruhe, 1997, pp. 955-961.
BibTeX data

S.P. Fekete,
"Geometric ideas for graph representation and for cooperative game theory."
Habilitationsschrift. Universit�t zu K�ln, 1997.

S.P. Fekete, J.Schepers.
"On higher-dimensional packing I: Modeling."
Technical Report ZPR 97-288
Note: There is a more recent journal version! (In Mathematics of Operations Research, see above.)
BibTeX data

S.P. Fekete, J.Schepers.
"On higher-dimensional packing II: Bounds."
Technical Report ZPR 97-289
Note: There is a more recent journal version! (In Mathematical Methods of Operations Research, see above.)
BibTeX data

S.P. Fekete, J.Schepers.
"On higher-dimensional packing III: Exact algorithms."
Technical Report ZPR 97-290
Note: There is a more recent journal version! (To appear in Operations Research, see above.)
BibTeX data

S.P. Fekete, M. Schmitt.
"Traveling salesmen in the age of competition."
Technical Report ZPR 97-266. 1997, 5 pages.
BibTeX data

1996

S.P. Fekete, S.Khuller, M.Klemmstein, B.Raghavachari, N.Young.
"Finding low-weight bounded-degree trees."
Proceedings of the 5th International Integer Programming and Combinatorial Optimization Conference (IPCO 96), 1996, pp. 105-117.
BibTeX data

O. Bastert, S.P. Fekete.
"Geometrische Verdrahtungsprobleme."
Technical Report ZPR 96-247. 1996, 81 pages.
BibTeX data

S.P. Fekete, M. Houle, S. Whitesides.
"New results on a visibility representation of graphs in 3D."
Graph Drawing 95,
Springer Lecture Notes in Computer Science, vol. 1072, 1996, pp. 234-241.
BibTeX data

S.P. Fekete, H. Meijer,
"Rectangle and box visibility graphs in 3D."
Proceedings 12th European Workshop on Computational Geometry 9 (1996), pp. 31-34.
BibTeX data

1995

S.P. Fekete, M.Klemmstein.
"Worst-case ratios for bounded-degree trees."
Proceedings of the 4th Biannual Twente Workshop on Graph Theory and Discrete Optimization. Twente, 1995, pp. 103-106.
BibTeX data

1994

P. Bose, H. Everett, S.P. Fekete, M. Houle, A. Lubiw, H. Meijer, K. Romanik, G. Rote, T. Shermer, S. Whitesides.
"On a visibility representation of graphs in three dimensions."
In: D. Avis, P. Bose, eds.: Snapshots of Computational and Discrete Geometry, 3 (1994), Montreal, pp. 2-25.
BibTeX data

1993

S.P. Fekete, W.R. Pulleyblank.
"Minimum area polygons."
Proceedings of the Ninth Annual ACM Symposium on Computational Geometry, 1993, pp. 173-182.
BibTeX data

E.M. Arkin, S.P. Fekete, J.S.B.Mitchell,
"The lawnmower problem."
Proceedings of the Fifth Canadian Conference on Computational Geometry. 1993, pp. 461-466.
BibTeX data

U. Faigle, S.P. Fekete, W.Hochst�ttler, W.Kern.
"Approximating the core of Euclidean TSP games."
In: A. Bachem, U. Derigs, M. J�nger, R. Schrader, Operations Research '93, pp. 153-156.
BibTeX data

P. Bose, H. Everett, S.P. Fekete, M. Houle, A. Lubiw, H. Meijer, K. Romanik, G. Rote, T. Shermer, S. Whitesides.
"3-dimensional visibility representation of graphs."
Graph Drawing 93.
BibTeX data

S.P. Fekete, W.R. Pulleyblank.
"Backward Error Analysis for the Travelling Salesman Problem: Generalized Convexity."
Technical Report ZPR 93-142, 1993.
BibTeX data

1992

S.P. Fekete,
"Geometry and the Travelling Salesman Problem."
Ph.D. thesis. University of Waterloo, 1992.
BibTeX data

S.P. Fekete,
"Finding all anchored squares in a convex polygon in subquadratic time."
Proceedings of the Fourth Canadian Conference on Computational Geometry, 1992, pp. 71-76.
BibTeX data

Last update: Tue Sep 15 17:51:15 CEST 2009
Sandor Fekete, s.fekete AT tu-bs.de