Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Robustness of Convergence Proofs in Numerical Methods in Unconstrained Optimization Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

A Linearly-Growing Conversion from the Set Splitting Problem to the Directed Hamiltonian Cycle Problem

verfasst von : Michael Haythorpe, Jerzy A. Filar

Erschienen in: Optimization and Control Methods in Industrial Engineering and Construction

Verlag: Springer Netherlands

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We consider a direct conversion of the, classical, set splitting problem to the directed Hamiltonian cycle problem. A constructive procedure for such a conversion is given, and it is shown that the input size of the converted instance is a linear function of the input size of the original instance. A proof that the two instances are equivalent is given, and a procedure for identifying a solution to the original instance from a solution of the converted instance is also provided. We conclude with two examples of set splitting problem instances, one with solutions and one without, and display the corresponding instances of the directed Hamiltonian cycle problem, along with a solution in the first example.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Robust Optimal Control of Continuous Linear Quadratic System Subject to Disturbances
Nächstes Kapitel Optimum Confidence Interval Analysis in Two-Factor Mixed Model with a Concomitant Variable for Gauge Study
Fußnoten
1
In fact, due to the nature of the construction, if the element appears in \(q\) subsets, then exactly \(q\) type 2 forced paths must occur here.
 
Literatur
1.
2.
Baniasadi P, Ejov V, Filar JA, Haythorpe M, Rossomakhine S (2012) Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem. Math Program Comput (submitted 2012) doi:10.​1007/​s12532-013-0059-2
3.
Borkar VS, Ejov V, Filar JA, Nguyen GT (2012) Hamiltonian cycle problem and Markov chains. Springer, New YorkCrossRefMATH
4.
Chang W-L, Guo M, Ho M (2004) Towards solutions of the set-splitting problem on gel-based DNA computing. Future Gener Comput Syst 20(5):875–885CrossRef
5.
Chen J, Lu S (2007) Improved algorithms for weighted and unweighted set splitting problems. In: COCOON, vol 4598 of, Lecture Notes in Computer Science, pp 537–547
6.
Cook S (1971) The complexity of theorem proving procedures. In: Proceedings of the third annual ACM symposium on theory of computing, pp. 151–158
7.
Dehne FKHA, Fellows MR, Rosamond FA (2003) An FPT algorithm for set splitting. In: WG, Lecture notes in computer science, vol 2880, pp 180–191
8.
9.
Erdős P, Hajnal A (1961) On a property of families of sets. Acta Math Hung 12(1–2):87–123
10.
Garey MR, Johnson DS (1979) Computers and intractiability: a guide to the theory of NP-completeness. WH Freeman and Company, New York
11.
Karp R (1972) Reducibility among combinatorial problems. In: Miller Raymond E, Thatcher James W (eds) Complexity of computer computations. Plenum, New York, pp 85–103CrossRef
12.
Kugele S (2006) Efficient solving of combinatorial problems using SAT-solvers. Ph.D Thesis, Technische Universität München
13.
Lokshtanov D, Saurabh S (2009) Even faster algorithm for set splitting!. In: Parameterized and exact computation: 4th international workshop, IWPEC 2009, Copenhagen, pp. 288–299, Sept 2009
14.
Miller EW (1937) On a property of families of sets. Comptes Rendus Vars 30:31–38
15.
Radhakrishnan J, Srinivasan A (2000) Improved bounds and algorithms for hypergraph 2-coloring. Random Struct Algorithms 16(1):4–32CrossRefMATHMathSciNet
Metadaten
Titel
A Linearly-Growing Conversion from the Set Splitting Problem to the Directed Hamiltonian Cycle Problem
verfasst von
Michael Haythorpe
Jerzy A. Filar
Copyright-Jahr
2014
Verlag
Springer Netherlands
Buch
Optimization and Control Methods in Industrial Engineering and Construction

Print ISBN: 978-94-017-8043-8

Electronic ISBN: 978-94-017-8044-5

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-94-017-8044-5_3

Neuer Inhalt

    Bildnachweise