TY - CONF
AB - We study graph properties which are testable for bounded degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. It is believed that almost all, even very simple graph properties require a large complexity to be tested for arbitrary (bounded degree) graphs. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. We call a graph family non-expanding if every graph in this family is not a weak expander (its expansion is O(1/log2 n), where n is the graph size). A graph family is hereditary if it is closed under vertex removal. Similarly, a graph property is hereditary if it is closed under vertex removal. Next, we call a graph property Π to be testable for a graph family F if for every graph G ε F, in time independent of the size of G we can distinguish between the case when G satisfies property Π and when it is far from every graph satisfying property Π. In this paper we prove thatIn the bounded degree graph model, any hereditary property is testable if the input graph belongs to a hereditary and non-expanding family of graphs.As an application, our result implies that, for example, any hereditary property (e.g., k-colorability, H-freeness, etc.) is testable in the bounded degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before and prior to our work, in the bounded degree graph model very few graph properties have been known to be testable for any graph classes.
AU - Sohler, Christian
AU - Czumaj, Artur
ID - 18655
SN - 9780898716245
T2 - Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA'07)
TI - On Testable Properties in Bounded Degree Graphs
ER -
TY - GEN
AU - Peckhaus, Volker
ID - 18650
T2 - Zentralblatt für Mathematik und ihre Grenzgebiete [Zbl. 1123.01019]
TI - Bolzano, Bernard, Briefe an Josef Sommer und andere (1812–1848), hg. v. Jan Berg, Frommann-Holzboog: Stuttgart-Bad Cannstatt 2005 (Bernard Bolzano-Gesamtausgabe, III.5.1)
ER -
TY - CONF
AU - Sohler, Christian
AU - Czumaj, Artur
ID - 18662
T2 - Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS'07)
TI - Small Space Representations for Metric Min-Sum k-Clustering and their Applications
ER -
TY - GEN
AU - Peckhaus, Volker
ID - 18821
T2 - Mathematical Reviews [MR 2007a:03002]
TI - De Mol, Liesbeth, “Closing the Circle: An Analysis of Emil Post’s Early Work”, Bulletin of Symbolic Logic 12 (2006), 267–289
ER -
TY - BOOK
AU - Eke, Norbert Otto
ID - 19007
TI - Wort/Spiele. Drama – Film – Literatur
ER -
TY - CHAP
AU - Seng, Eva- Maria
ID - 19139
T2 - Jülicher Geschichtsblätter Bd. 73
TI - „Zwischen Utopie und Realität. Die ‚Idealstadt’ Jülich als Ausdruck des frühneuzeitlichen Ordnungsdenkens“
VL - Bd. 73
ER -
TY - CHAP
AU - Eke, Norbert Otto
ED - Schörkhuber, Eva
ID - 19336
T2 - Was einmal wirklich war. Zum Werk Robert Menasses
TI - „Nichts, was einen Anfang hatte, ist unendlich.“ Robert Menasses Arbeit an der Differenz – Die Zerstörung der Welt als Wille und Vorstellung. Frankfurter Poetikvorlesungen
ER -
TY - CONF
AU - Briest, Patrick
AU - Krysta, Piotr
ID - 19689
T2 - Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA)
TI - Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing
ER -
TY - CHAP
AU - Büker, Petra
ED - Vorst, Claudia
ED - Grosser, Sabine
ED - Eckhardt, Juliane
ED - Burrichter, Rita
ID - 19696
T2 - Ästhetisches Lernen. Fachdidaktische Grundfragen und praxisorientierte Konzepte im interdisziplinären Kontext von Lehrerbildung und Schule
TI - „Als die Schmetterlinge kamen“ – ein empirisches Unterrichtsforschungsprojekt zum ästhetischen Lernen im interkulturell orientierten Literaturunterricht der Grundschule
ER -
TY - CONF
AB - Current research in Micro, Nano and Swarm Robots as results of the European projects Miniman, MiCRoN and I-SWARM will be presented. First, the design and the control of 5 to 10cm3 sized mobile micro robots with five degrees of freedom will be shown. They can handle miniaturized parts as for example an optical component or a biological cell with a size in the micrometre-area with an accuracy of 100nm under a microscope or a raster-electron microscope. Second, the design and the control of a 1cm3-sized mobile untethered micro robot will be demonstrated. Here, the robot consists of five parts: the Piezzo locomotion module, the micro control unit, the communication unit, the navigation system and the micro gripper. The mobile robot can be guided and positioned in an arena with an accuracy of 5 micrometre and can be programmed and controlled over the wireless communication unit. Third, the design and the control of 3 × 3 × 3 mm3 sized micro-/nanorobots with 2 degrees of freedom will be presented. The transmission of energy and the communication between the robots is realized via infrared. The robot controller is fully integrated and has limited functionalities. Via basic sensors communication functions and elementary rules and behaviours the micro robot can act in a swarm consisting of hundreds and thousands of robots. Future applications could be monitoring-, inspection-, exploring-tasks etc. of big areas or objects.
AU - Hamann, Heiko
AU - Szymanski, Marc
AU - Wörn, Heinz
AU - Estana, Ramon
AU - Xie, Ming
AU - Dubowsky, Steven
ID - 20434
T2 - Advances in Climbing and walking robots. Proceedings of 10th International Conference (CLAWAR'07), Singapore, July 16-18
TI - From Micro to Nano and Swarm Robotics
ER -