81. Traveling Salesman Problem These pages report the history of the TSP and ongoing work to solve large instances. http://www.tsp.gatech.edu//

82. Capillary Multi-path Routing With Forward Error Correction By Emin Gabrielyan. http://switzernet.com/people/emin-gabrielyan/060124-capillary-aron-article/

Capillary multi-path routing with Forward Error Correction Emin Gabrielyan Switzernet – EPFL Lausanne Switzerland HTML PDF DOC Table of contents: I. Introduction II. Path Diversity Spread Routing ... Relative links I. Introduction Media streaming is becoming increasingly important in Internet. The major cause for multimedia quality degradation in IP-networks is packet loss. Packet loss occurs in network due to bursts and link failures or packets may be dropped in the application, if they are received too late. Forward Error Correction is a mechanism that may allow the streaming application to overcome losses without utilizing retransmissions. Real-time media or files sent over the internet are chopped into packets, and each packet is either received without error or not received. Packetized communications over internet thus behave like erasure channels and the erasure resilient FEC codes, such as Reed Solomon or another Maximum Distance Separable (MDS) code can be applied on the packet level to a stream of UDP (User Datagram Protocol) data packets. With the proper amount of redundant data included in the stream of transmitted packets, erasure resilient FEC can mitigate the impact of packet loss on the data. For numerous packetized applications, employment of erasure resilient FEC codes offered spectacular results: in satellite feedback-less broadcasts of recurrent voluminous updates of GPS (Global Positioning System) maps to millions of motor vehicles under the condition of arbitrary fragmental visibility due to their locations and trajectories: tunnels, underground parking, buildings and garages [

83. Graph Theory Trees . An acyclic graph (also known as a forest) is a graph with no cycles. A tree is a connected acyclic graph. Thus each component of a forest is tree, and any tree is a http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/trees.htm

Trees An acyclic graph (also known as a forest) is a graph with no cycles. A tree is a connected acyclic graph. Thus each component of a forest is tree, and any tree is a connected forest. Theorem The following are equivalent in a graph G with n vertices. G is a tree. There is a unique path between every pair of vertices in G. G is connected, and every edge in G is a bridge. G is connected, and it has (n - 1) edges. G is acyclic, and it has (n - 1) edges. G is acyclic, and whenever any two arbitrary nonadjacent vertices in G are joined by and edge, the resulting enlarged graph G' has a unique cycle. G is connected, and whenever any two arbitrary nonadjacent vertices in G are joined by an edge, the resulting enlarged graph has a unique cycle. Generally speaking , algorithms associated with trees can be divided into three types. Algorithms for searching and labeling a given tree. Algorithms for constructing various types of tree. Algorithms for counting trees of a particular type. Tree A tree is a connected graph which contain no cycles.

84. Counting Hamilton Cycles In Product Graphs By Frans Faase. http://www.iwriteiam.nl/counting.html

Counting Hamilton cycles in product graphs This is a subject that has intrigued me as long as I could write computer programs. I have always been interested by seemingly simple problems that result in complex answers. This subject interested me even before I knew it had a name. Actually, it all started with Hamilton paths. The very beginning It all started with a idea that I had, about a program that would draw a snake on the screen. The snake would start at one place in a box, and then extend itself until it could not go further, after which it would shrink again, to seek another path. A snap-shot of the screen could look like: A Fortran program A little later, I wrote a FORTRAN program, that would write down movements that the snake would make, for a certain problem. This would generate output like this: nnnnwsssswnnnnwsssswnnnn wnnn se wnn ssen esw And so on for many pages... (An n stands for going North

85. Math Forum - Problems Library - Discrete Math, Combinatorics TOPICS. This page graph theory . About Levels of Difficulty. Discrete Math combinatorics graph theory logic patterns/recursion proof social choice http://mathforum.org/library/problems/sets/dm_graphtheory.html

Become a Member Learn about Membership TOPICS This page: graph theory About Levels of Difficulty Discrete Math combinatorics graph theory logic patterns/recursion ... PoW Library Teacher Support Page Available Problem Accepts Submissions Discrete Math: Graph Theory Graph theory is a very large topic within discrete mathematics. Graph theory involves working with diagrams that consist of points, called vertices, and line segments, called edges. A few of the topics within graph theory include critical paths (Mud Slides and Critical Paths), minimal cost spanning trees (Minimal Minnie's Cost), Euler paths/circuits (The West Nile Virus Carrying Mosquito Problem), and vertex coloring (Beds of Flowers). The problems below include these types of problems, as well as other problems that involve graphs. For background information elsewhere on our site, explore the High School Discrete Math area of the Ask Dr. Math archives. To find relevant sites on the Web, browse and search Discrete Mathematics in our Internet Mathematics Library.

86. Merlins-World An approach to solve the asymmetric travelling salesman problem using linear optimisation with a polynomial bounded set of constraints. http://www.merlins-world.de

Welcome to the page of M ERLIN The polynomial-bounded solution for the Traveling Salesman Problem You can find here: Something about the background Link to the corresponding article in the journal Applied Mathematics and Computation (Volume 186-1, 1 March 2007, Pg. 907-914) A presentation with a summary description of the MERLIN approach ( pdf Input Files in LP-Format for a linear solver Output Files of the optimization Validation results coming soon... P=NP! © Joachim Mertz, 2006 Contact tsp@merlins-world.de

87. Harmonious Colourings Notes and bibliography by Keith Edwards. http://www.maths.dundee.ac.uk/~kedwards/harmcol.html

Harmonious Colourings and Achromatic Number A vertex colouring of a graph is an assignment of colours to the vertices, with the requirement that adjacent vertices receive distinct colours. A harmonious colouring is a vertex colouring with the added requirement that each pair of colours appears together on at most one edge. The harmonious chromatic number of a graph is the minimum number of colours in a harmonious colouring of the graph. A closely related concept is the achromatic number of a graph, which is the greatest number of colours in a vertex colouring such that for each pair of colours, there is at least one edge whose endpoints have those colours. Such a colouring is called a complete colouring Click here for a bibliography of papers on harmonious colourings and achromatic number (89k, last updated 5 September 2007). This is also available as a pdf file. It is intended to be a comprehensive list; please email me if you know of any omissions or errors, or if you would like a copy of the LaTeX source file. Click here to see a list of my papers on the subject Detachments and Exact Colourings Another related concept is a detachment of a graph. A detachment of a graph G is formed by splitting each vertex into one or more subvertices, and sharing the incident edges arbitrarily among the subvertices. Thus a detachment of G has at least as many vertices as G, and the same number of edges as G.

88. Eric Filiol, Edouard Franc, Alessandro Gubbioli, Benoit Moquet, Guillaume Roblot By Eric Filiol, Edouard Franc, Alessandro Gubbioli, Benoit Moquet and Guillaume Roblot. http://vx.netlux.org/lib/aef05.html

English Deutsch Español Italiano Polski Bookmark VX Heavens Library Collection ... Forum Combinatorial Optimisation of Worm Propagation on an Unknown Network Eric Filiol Edouard Franc Alessandro Gubbioli Benoit Moquet ... Guillaume Roblot PROCEEDINGS OF WORLD ACADEMY OF SCIENCE, ENGINEERING AND TECHNOLOGY VOLUME 23, pp.373-379 ISSN 1307-6884 August 2007 Download PDF (465.73Kb) (You need to be registered on forum Back to index Comments E. Filiol is with the Lab. of Virology and Cryptology, ESAT, B.P. 18, 35998 Rennes Arm´ees (France), Email: eric.filiol@esat.terre.defense.gouv.fr. He is also Full Professor at ESIEA - Laval filiol@esiea.fr Edouard Franc, Benoit Moquet and Guillaume Roblot are with the Lab. of Virology and Cryptology, ESAT, B.P. 18, 35998 Rennes Arm´ees (France) and with the French Navy, ESCANSIC, Saint Mandrier, France. Alessandro Gubbioli is with the Polytecnico di Milano, Milan, Italy and was on stay at the Lab. of Virology and Cryptology, ESAT for this research work. Abstract Worm propagation profiles have significantly changed since 2003-2004: sudden world outbreaks like Blaster or Slammer have progressively disappeared and slower but stealthier worms appeared since, most of them for botnets dissemination. Decreased worm virulence results in more difficult detection. In this paper, we describe a stealth worm propagation model which has been extensively simulated and analysed on a huge virtual network. The main features of this model is its ability to infect any Internet-like network in a few seconds, whatever may be its size while greatly limiting the reinfection attempt overhead of already infected hosts. The main simulation results shows that the combinatorial topology of routing may have a huge impact on the worm propagation and thus some servers play a more essential and significant role than others. The real-time capability to identify them may be essential to greatly hinder worm propagation.

89. Traveling Salesman Problem Generator Generates a Traveling Salesman Problem map and data for a given set of US cities. http://www.60feet6.com/research/usa_tsp_tech.html

TSP Generator Research Sean Forman You Are Here On-line TSP Generator by Sean Forman sforman@sju.edu http://www.sju.edu/~sforman/ Introduction Hamiltonian Circuits and the Traveling Salesman Problem (TSP) are often covered as part of Graph Theory sections in many mathematics courses. TSP is taken from the idea of a salesperson getting up in the morning and then having to visit a large number of clients and then return home at the end of the day. The salesman wishes to find the shortest route to visit all of the clients. Thinking mathematically, this requires the determination of the shortest circuit (a tour that begins and ends in the same city) connecting a given set of cities. Typically, students are introduced to the TSP and shown several common heuristics that can be used to find an approximate (sometimes optimal) solution. I have designed a web application, TSP Generator, that takes as an input a list of user-provided cities (up to 30), and produces a variety of outputs useful to our instructors and students covering this subject. I use this tool as a teaching aid. It allows me to quickly generate example, real-life problems for the students to solve. Given a list of cities, TSP Generator produces the

90. Home - Matrix Graph Grammars Algebraic approach to graph dynamics and graph grammars, using logics, functional analysis and tensor algebra. http://www.mat2gra.info

91. Linear Spaces Of A Graph Some proofs by S C Locke. http://www.math.fau.edu/locke/LinearSp.htm

Linear Spaces of a Graph How to contact me This material comes from some notes for a University of Waterloo course taught by Herb Shank (c. 1975). I have an export of a maple worksheet, showing these operators: http://www.math.fau.edu/Locke/courses/GraphTheory/LinSpGen.htm Back to the Graph Theory Index Let G be a finite, connected, directed graph. If the vertex set of G is ,v ,...,v m and the edge set of G is ,e ,...,e n , then it is useful to consider an oriented edge to be an ordered pair of vertices (say tip first, then tail). So: e i =(v s ,v r would indicate that edge e i is directed from v r to v s If F is a field, and S is a finite set, let F denote the set of all linear combinations of elements of S with coefficients in F . If addition and scalar multiplication are "coordinatewise", then F is a vector space over F having S as one of its bases. Where unambiguous, the subscript F may be omitted. Despite this notational convention, F is important enough to have a special name, C F (G) . When it is convenient and no misinterpretation is possible, we will write

92. Graphs Glossary Short definitions with cross-references by Bill Cherowitzo. http://www-math.cudenver.edu/~wcherowi/courses/m4408/glossary.htm

93. List Of Small Graphs Information System on Graph Class Inclusions, University of Rostock. http://wwwteo.informatik.uni-rostock.de/isgci/smallgraphs.html

ISGCI home All classes Java References Contents Graphs ordered alphabetically Graphs ordered by number of vertices 3 vertices 4 vertices ... Special families of graphs Graphs ordered alphabetically Note that complements are usually not listed. So for e.g. co-fork, look for fork. Only individual graphs are listed, not families or configurations. ∪ K cross star X ... X Graphs ordered by number of vertices 3 vertices - Graphs are ordered by increasing number of edges in the left column. = co-triangle triangle = K = C back to top P P back to top 4 vertices - Graphs are ordered by increasing number of edges in the left column. K K = W back to top co-diamond diamond = K - e = 2-fan back to top co-paw paw = 3-pan back to top C C = K back to top claw = K co-claw back to top P Self complementary back to top 5 vertices - Graphs are ordered by increasing number of edges in the left column. K - e + e = K K - e back to top W W back to top P ∪ P P ∪ P back to top co-gem gem = 3-fan back to top K K back to top K K = K ∪ K back to top co-butterfly = C ∪ K butterfly back to top fork = chair co-fork = kite = co-chair = chair back to top co-dart dart back to top P

94. Advanced Topics In Graph Algorithms Lecture notes by Ron Shamir. http://www.math.tau.ac.il/~rshamir/atga/atga.html

Advanced Topics in Graph Algorithms This archive contains material on the course taught by Ron Shamir in the department of Computer Science of Tel-Aviv university , on 10/91-2/92 (Fall 92), 4-6/94 (Spring 94) and 4-6/97 (Spring 97). This was a one-semester graduate course open also to seniors, with one three-hour meeting each week. The course emphasized algorithmic and structural aspects of "nice" graph families, in particular perfect graphs, interval graphs, chordal graphs and comparability graphs. In Fall 92 the course was based to a large extent on the classic book of Martin C. Golumbic "Algorithmic Graph Theory and Perfect Graphs' (Academic Press, 1980), and in some parts also on the manuscript "The Art of Combinatorics", by Douglas B. West. The Spring 94 and Spring 97 course had a similar basis, but emphasized more recent material, and made a lot of reference to applications in molecular biology. (See the webpage Algorithms for Molecular Biology for much more on these aspects.) Material available: Detailed course outline Spring 97 (HTML) Spring 94 (ASCII) Fall 92 (ASCII) Spring 1997 course material (unorganized; some links were not updated and some material is readable only to TAU browsers. Sorry.)

95. Degree-Diameter Table For Graphs With references and further links. http://maite71.upc.es/grup_de_grafs/grafs/taula_delta_d.html

96. Gordon Royle's Cubic Graphs List of cubic graphs maintained by Gordon Royle. http://www.csse.uwa.edu.au/~gordon/remote/cubics/

Cubic Graphs This page provides access to the ever popular listings of cubic graphs together with a variety of data relating to these graphs. Please note that these pages are being developed incrementally on an "as-needed" basis, so if you want anything, then just ask me on gordon@cs.uwa.edu.au and unless its a bad time, then I will probably oblige. Most of this work originates from my PhD thesis Constructive Enumeration of Graphs , though the techniques used there are now largely obsolete. At present the best cubic graph generation program is written by, and available from Gunnar Brinkmann. The data from the snarks section was generated by Gunnar, so thanks to him for letting me incorporate it into this database. Table of Contents All cubic graphs Properties Snarks Chromatic Polynomials ... Chromatic Roots All cubic graphs Exact numbers of cubic graphs are known by results of Robinson and Wormald for values up to 40 vertices. The cubic graphs on up to 20 vertices, together with some smaller families of high girth cubic graphs on higher numbers of vertices are available. The larger numbers in the table, other than the Robinson/Wormald results are due to Gunnar Brinkmann. Each number in the table below is a link to a file of graphs in format. The largest file is the cubics on 22 vertices at 300Mb.

97. Gordon Royle's Small Graphs Gordon Royle s tables of small graphs with Maple software. http://www.csse.uwa.edu.au/~gordon/remote/graphs/

Small Graphs This site is intended to collate much of the data about small graphs that I have to keep on recomputing. It is primarily designed for my own use, but anyone else is free to check out the numbers or the graphs. If you are interested in small graph data that is not here, then feel free to mail me at gordon@maths.uwa.edu.au because I may have just not got around to installing it. Table of Contents Numbers of graphs Numbers of bipartite graphs Trees on up to 20 vertices Colourings of small graphs ... Class 2 graphs Numbers of graphs The exact numbers of graphs on n vertices and e edges can be computed by using Polya enumeration theory. This enables us to produce a series of tables of the following format. The tables were produced by a Maple program written with Brendan McKay (well, he wrote it after joint discussions). Graphs with 4 vertices #edges Connected graphs All graphs Total Tables of this nature are available for the graphs on 1-16 vertices. 1 vx 2 vx 3 vx 4 vx ... 16 vx Bipartite graph The following table gives the number of connected bipartite graphs separated according to the size of the bipartition. Each row corresponds to a fixed number of vertices, while each column refers to the smaller part of the bipartition. Thus the entry 34 for 7 vertices and m=3 indicates that there are 34 conected bipartite graphs on 7 vertices with partition of size (3,4).

98. Four Color Theorem A Brief Historical Insight An essay by Dominic Verderaime. http://student.adams.edu/~verderaimedj/finalEssay/

99. Some Open Problems Compiled by Jerry Spinrad. http://www.vuse.vanderbilt.edu/~spin/open.html

Send comments or new problems to include to spin@vuse.vanderbilt.edu

100. Some Open Problems Open problems and conjectures concerning the determination of properties of families of graphs. http://www.eecs.umich.edu/~qstout/constantques.html

Some Open Problems and Conjectures These problems and conjectures concern the determination of properties of families of graphs. For example, one property of a graph is its domination number. For a graph G , a set S of vertices is a dominating set if every vertex of G is in S or adjacent to a member of S . The domination number of G is the minimum size of a dominating set of G . Determining the domination number of a graph is an NP-complete problem, but can often be done for many graphs encountered in practice. One topic of some interest has been to determine the dominating numbers of grid graphs (meshes), which are just graphs of the form P(n) x P(m) , where P(n) is the path of n vertices. Marilynn Livingston and I showed that for any graph G , the domination number of the family G x P(n) has a closed formula (as a function of n ), which can be found computationally. This appears in M.L. Livingston and Q.F. Stout, ``Constant time computation of minimum dominating sets'', Congresses Numerantium (1994), pp. 116-128. Abstract Paper.ps

A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z

Page 5     81-100 of 106    Back | 1  | 2  | 3  | 4  | 5  | 6  | Next 20