The first use of graph theory is dated to 1735. Swiss mathematician and physicist, Leonhard Euler, formulated theorems and definitions related to graphs. Euler was inspired by a real problem regarding crossing bridges in Königsberg (east Prussia, also known as Królewiec, Kaliningrad). He tried to take a walk around the city in such a way that each of the seven bridges was crossed only once. Finally, Euler proved that it was impossible, simultaneously solving the puzzles with the application of graph theory. Nowadays, such a theory is used in numerous fields of science and practical approaches. This chapter presents notations and definitions related to the graph theory. Furthermore, perfect graphs and comparability graphs are introduced. New theorems, lemmas, and algorithms regarding recognition and coloring of comparability graphs are proposed.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Aho AV, Hopcroft JE, Ullman J (1983) Data structures and algorithms, 1st edn. Addison-Wesley Longman Publishing Co. Inc, Boston
MATH
2.
Bang-Jensen J, Gutin GZ (2007) Digraphs: theory, algorithms and applications, 1st edn. Springer, Incorporated
MATH
3.
Berge C (1973) Graphs and hypergraphs. North-Holland Pub. Co.; American Elsevier Pub. Co., Amsterdam, New York
MATH
4.
Bron C, Kerbosch J (1973) Algorithm 457: finding all cliques of an undirected graph. Commun ACM 16(9):575–577
CrossRefMATH
5.
Chandler D, Chang M-S, Kloks T, Liu J, Peng S-L (2006) Partitioned probe comparability graphs. In: Fomin F (ed) Graph-theoretic concepts in computer science, vol 4271., Lecture notes in computer scienceSpringer, Heidelberg, pp 179–190
CrossRef
6.
Corno F, Prinetto P, Sonza Reorda M (1995) Using symbolic techniques to find the maximum clique in very large sparse graphs. In: EDTC ’95: Proceedings of the 1995 European conference on design and test, Washington, DC, USA, 1995. IEEE Computer Society, p 320
7.
Cornuéjols G, Liu X, Vuskovic K (2003) A polynomial algorithm for recognizing perfect graphs. In: FOCS. IEEE Computer Society Press, pp 20–27
8.
Diestel R (2000) Graph theory. Springer, New York (Electronic Edition)
9.
Golumbic MC (1977) The complexity of comparability graph recognition and coloring. Computing 18(3):199–208
MathSciNetCrossRefMATH
10.
Golumbic MC (1980) Algorithmic graph theory and perfect graphs
11.
Grötschel M, Lovász L, Schrijver A (1984) Polynomial algorithms for perfect graphs. Perfect graphs, volume 21 of Annals of Discrete Mathematics. North-Holland, Amsterdam, pp 325–356
12.
Habib M, McConnell R, Paul C, Viennot L (2000) Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoret Comput Sci 234(1–2):59–84
MathSciNetCrossRefMATH
13.
Harary F (1994) Graph theory. Addison-Wesley, Reading
MATH
14.
Homer S, Selman A (2001) Computability and complexity theory. In: Texts in computer science. Springer
15.
Jensen TR, Toft B (1995) Graph coloring problems. Wiley-Interscience, New York
MATH
16.
Johnson DS, Papadimitriou CH, Yannakakis M (1988) On generating all maximal independent sets. Inf Process Lett 27(3):119–123
MathSciNetCrossRefMATH
17.
Kelly D (1985) Comparability graphs. In: Rival I (ed) Graphs and order, vol 147., NATO ASI seriesSpringer, Netherlands, pp 3–40
CrossRef
18.
Kubale M (2004) Graph colorings. American Mathematical Society
19.
Lovász L (1972) Normal hypergraphs and the weak perfect graph conjecture. Discrete Math 2:253–267
MathSciNetCrossRefMATH
20.
Lovász L (1983) Perfect graphs. In: Beineke L, Wilson R (eds) Selected topics in graph theory, vol 2. Academic Press
21.
Makino K, Uno T (2004) New algorithms for enumerating all maximal cliques. In: Hagerup T, Katajainen J (eds) Algorithm theory—SWAT 2004, vol 3111., Lecture notes in computer scienceSpringer, Heidelberg, pp 260–272
CrossRef
22.
Shamir R (1994) Advanced topics in graph algorithms
23.
Tomita E, Tanaka A, Takahashi H (2006) The worst-case time complexity for generating all maximal cliques and computational experiments. Theoret Comput Sci 363(1):28–42
MathSciNetCrossRefMATH
24.
West DB (2000) Introduction to graph theory, 2nd edn. Prentice Hall
Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.
Bedingt durch die Altersstruktur vieler Kabelverteilnetze mit der damit verbundenen verminderten Isolationsfestigkeit oder durch fortschreitenden Kabelausbau ist es immer häufiger erforderlich, anstelle der Resonanz-Sternpunktserdung alternative Konzepte für die Sternpunktsbehandlung umzusetzen. Die damit verbundenen Fehlerortungskonzepte bzw. die Erhöhung der Restströme im Erdschlussfall führen jedoch aufgrund der hohen Fehlerströme zu neuen Anforderungen an die Erdungs- und Fehlerstromrückleitungs-Systeme. Lesen Sie hier über die Auswirkung von leitfähigen Strukturen auf die Stromaufteilung sowie die Potentialverhältnisse in urbanen Kabelnetzen bei stromstarken Erdschlüssen. Jetzt gratis downloaden!
