Eingang zum Volltext


Urheberrechtshinweis / Copyright notice

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://opus.kobv.de/zib/volltexte/2008/1119/


Berthold, Timo ; Pfetsch, Marc E.

Detecting Orbitopal Symmetries

pdf-Format:
Dokument 1.pdf (115 KB)
ps-Format:
Dokument 1.ps (333 KB)


Kurzfassung in Englisch

Orbitopes can be used to handle symmetries which arise in integer programming formulations with an inherent assignment structure. We investigate the detection of symmetries appearing in this approach. We show that detecting so-called orbitopal symmetries is graph-isomorphism hard in general, but can be performed in linear time if the assignment structure is known.

Freie Schlagwörter (deutsch): Symmetrie-Erkennung , Orbitope , Ganzzahlige Programmierung , Symmetrie-Brechung , Graphenisomorphie
Freie Schlagwörter (englisch): symmetry detection , orbitopes , integer programming , symmetry breaking , graph ismorphism
MSC - Klassifikation 52B12
MSC - Klassifikation 90C57
MSC - Klassifikation 90C10
MSC - Klassifikation 90C35
Abteilung: Optimierung
DDC-Sachgruppe: Mathematik
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 08-33
ISBN: 1438-0064
Quelle: Appeared in: Operations Research Proceedings 2008, Bernhard Fleischmann ... (eds.), 2009, pp. 433-438
Sprache: Englisch
Erstellungsjahr: 2008
Publikationsdatum: 14.08.2008
Bemerkung: printed version not available / keine gedruckte Version


Metadatensuche | Volltextsuche | Browsen | Die neuesten Publikationen | Veröffentlichen
Fragen und Anregungen an bibliothek@zib.de
Letzte Änderung: