Spelling suggestions: "subject:"fandom agraphs"" "subject:"fandom digraphs""
61 |
Threshold Phenomena in Random Constraint Satisfaction ProblemsConnamacher, Harold 30 July 2008 (has links)
Despite much work over the previous decade, the Satisfiability Threshold
Conjecture remains open. Random k-SAT, for constant k >= 3,
is just one family of a large number
of constraint satisfaction problems that are conjectured to have exact
satisfiability thresholds, but for which the existence and location of these
thresholds has yet to be proven.
Of those problems for which we are able to prove
an exact satisfiability threshold, each seems to be fundamentally different
than random 3-SAT.
This thesis defines a new family of
constraint satisfaction problems with constant size
constraints and domains and which
contains problems that are NP-complete and a.s.\ have exponential
resolution complexity. All four of these properties hold for k-SAT, k >= 3,
and the
exact satisfiability threshold is not known for any constraint
satisfaction problem
that has all of these properties. For each problem in the
family defined in this
thesis, we determine
a value c such that c is an exact satisfiability threshold if a certain
multi-variable function has a unique maximum at a given point
in a bounded domain. We
also give numerical evidence that this latter condition holds.
In addition to studying the satisfiability threshold, this thesis
finds exact
thresholds for the efficient behavior of DPLL using the unit clause heuristic
and a variation of the generalized unit clause heuristic,
and this thesis proves an analog
of a conjecture on the satisfiability of (2+p)-SAT.
Besides having similar properties as k-SAT, this new family of
constraint satisfaction problems
is interesting to study in its own right because it generalizes the
XOR-SAT problem and it has close ties
to quasigroups.
|
62 |
Threshold Phenomena in Random Constraint Satisfaction ProblemsConnamacher, Harold 30 July 2008 (has links)
Despite much work over the previous decade, the Satisfiability Threshold
Conjecture remains open. Random k-SAT, for constant k >= 3,
is just one family of a large number
of constraint satisfaction problems that are conjectured to have exact
satisfiability thresholds, but for which the existence and location of these
thresholds has yet to be proven.
Of those problems for which we are able to prove
an exact satisfiability threshold, each seems to be fundamentally different
than random 3-SAT.
This thesis defines a new family of
constraint satisfaction problems with constant size
constraints and domains and which
contains problems that are NP-complete and a.s.\ have exponential
resolution complexity. All four of these properties hold for k-SAT, k >= 3,
and the
exact satisfiability threshold is not known for any constraint
satisfaction problem
that has all of these properties. For each problem in the
family defined in this
thesis, we determine
a value c such that c is an exact satisfiability threshold if a certain
multi-variable function has a unique maximum at a given point
in a bounded domain. We
also give numerical evidence that this latter condition holds.
In addition to studying the satisfiability threshold, this thesis
finds exact
thresholds for the efficient behavior of DPLL using the unit clause heuristic
and a variation of the generalized unit clause heuristic,
and this thesis proves an analog
of a conjecture on the satisfiability of (2+p)-SAT.
Besides having similar properties as k-SAT, this new family of
constraint satisfaction problems
is interesting to study in its own right because it generalizes the
XOR-SAT problem and it has close ties
to quasigroups.
|
63 |
New approaches to integer programmingChandrasekaran, Karthekeyan 28 June 2012 (has links)
Integer Programming (IP) is a powerful and widely-used formulation for combinatorial problems. The study of IP over the past several decades has led to fascinating theoretical developments, and has improved our ability to solve discrete optimization problems arising in practice. This thesis makes progress on algorithmic solutions for IP by building on combinatorial, geometric and Linear Programming (LP) approaches.
We use a combinatorial approach to give an approximation algorithm for the feedback vertex set problem (FVS) in a recently developed Implicit Hitting Set framework. Our algorithm is a simple online algorithm which finds a nearly optimal FVS in random graphs. We also propose a planted model for FVS and show that an optimal hitting set for a polynomial number of subsets is sufficient to recover the planted subset.
Next, we present an unexplored geometric connection between integer feasibility and the classical notion of discrepancy of matrices. We exploit this connection to show a phase transition from infeasibility to feasibility in random IP instances. A recent algorithm for small discrepancy solutions leads to an efficient algorithm to find an integer point for random IP instances that are feasible with high probability.
Finally, we give a provably efficient implementation of a cutting-plane algorithm for perfect matchings. In our algorithm, cuts separating the current optimum are easy to derive while a small LP is solved to identify the cuts that are to be retained for later iterations. Our result gives a rigorous theoretical explanation for the practical efficiency of the cutting plane approach for perfect matching evident from implementations.
In summary, this thesis contributes to new models and connections, new algorithms and rigorous analysis of well-known approaches for IP.
|
64 |
Stochastic Geometry, Data Structures and Applications of Ancestral Selection GraphsCloete, Nicoleen January 2006 (has links)
The genealogy of a random sample of a population of organisms can be represented as a rooted binary tree. Population dynamics determine a distribution over sample genealogies. For large populations of constant size and in the absence of selection effects, the coalescent process of Kingman determines a suitable distribution. Neuhauser and Krone gave a stochastic model generalising the Kingman coalescent in a natural way to include the effects of selection. The model of Neuhauser and Krone determines a distribution over a class of graphs of randomly variable vertex number, known as ancestral selection graphs. Because vertices have associated scalar ages, realisations of the ancestral selection graph process have randomly variable dimensions. A Markov chain Monte Carlo method is used to simulate the posterior distribution for population parameters of interest. The state of the Markov chain Monte Carlo is a random graph, with random dimension and equilibrium distribution equal to the posterior distribution. The aim of the project is to determine if the data is informative of the selection parameter by fitting the model to synthetic data. / Foundation for Research Science and Technology Top Achiever Doctoral Scolarship
|
65 |
Stochastic Geometry, Data Structures and Applications of Ancestral Selection GraphsCloete, Nicoleen January 2006 (has links)
The genealogy of a random sample of a population of organisms can be represented as a rooted binary tree. Population dynamics determine a distribution over sample genealogies. For large populations of constant size and in the absence of selection effects, the coalescent process of Kingman determines a suitable distribution. Neuhauser and Krone gave a stochastic model generalising the Kingman coalescent in a natural way to include the effects of selection. The model of Neuhauser and Krone determines a distribution over a class of graphs of randomly variable vertex number, known as ancestral selection graphs. Because vertices have associated scalar ages, realisations of the ancestral selection graph process have randomly variable dimensions. A Markov chain Monte Carlo method is used to simulate the posterior distribution for population parameters of interest. The state of the Markov chain Monte Carlo is a random graph, with random dimension and equilibrium distribution equal to the posterior distribution. The aim of the project is to determine if the data is informative of the selection parameter by fitting the model to synthetic data. / Foundation for Research Science and Technology Top Achiever Doctoral Scolarship
|
66 |
Random graph processes and optimisationCain, Julie A Unknown Date (has links) (PDF)
Random graph processes are most often used to investigate theoretical questions about random graphs. A randomised algorithm can be defined specifically for the purpose of finding some structure in a graph, such as a matching, a colouring or a particular kind of sub graph. Properties of the related random graph process then suggest properties, or bounds on properties, of the structure. In this thesis, we use a random graph process to analyse a particular load balancing algorithm from theoretical computer science. By doing so, we demonstrate that random graph processes may also be used to analyse other algorithms and systems of a random nature, from areas such as computer science, telecommunications and other areas of engineering and mathematics. Moreover, this approach can lead to theoretical results on the performance of algorithms that are difficult to obtain by other methods. In the course of our analysis we are also led to some results of the first kind, relating to the structure of the random graph. / The particular algorithm that we analyse is a randomised algorithm for an off-line load balancing problem with two choices. The load balancing algorithm, in an initial stage, mirrors an algorithm which finds the k-core of a graph. This latter algorithm and the related random graph process have been previously analysed by Pittel, Spencer and Wormald, using a differential equation method, to determine the thresholds for the existence of a k-core in a random graph. We modify their approach by using a random pseudograph model due to Bollobas and Frieze, and Chvatal, in place of the uniform random graph. This makes the analysis somewhat simpler, and leads to a shortened derivation of the thresholds and other properties of k-cores.(For complete abstract open document)
|
67 |
Stochastic Geometry, Data Structures and Applications of Ancestral Selection GraphsCloete, Nicoleen January 2006 (has links)
The genealogy of a random sample of a population of organisms can be represented as a rooted binary tree. Population dynamics determine a distribution over sample genealogies. For large populations of constant size and in the absence of selection effects, the coalescent process of Kingman determines a suitable distribution. Neuhauser and Krone gave a stochastic model generalising the Kingman coalescent in a natural way to include the effects of selection. The model of Neuhauser and Krone determines a distribution over a class of graphs of randomly variable vertex number, known as ancestral selection graphs. Because vertices have associated scalar ages, realisations of the ancestral selection graph process have randomly variable dimensions. A Markov chain Monte Carlo method is used to simulate the posterior distribution for population parameters of interest. The state of the Markov chain Monte Carlo is a random graph, with random dimension and equilibrium distribution equal to the posterior distribution. The aim of the project is to determine if the data is informative of the selection parameter by fitting the model to synthetic data. / Foundation for Research Science and Technology Top Achiever Doctoral Scolarship
|
68 |
Stochastic Geometry, Data Structures and Applications of Ancestral Selection GraphsCloete, Nicoleen January 2006 (has links)
The genealogy of a random sample of a population of organisms can be represented as a rooted binary tree. Population dynamics determine a distribution over sample genealogies. For large populations of constant size and in the absence of selection effects, the coalescent process of Kingman determines a suitable distribution. Neuhauser and Krone gave a stochastic model generalising the Kingman coalescent in a natural way to include the effects of selection. The model of Neuhauser and Krone determines a distribution over a class of graphs of randomly variable vertex number, known as ancestral selection graphs. Because vertices have associated scalar ages, realisations of the ancestral selection graph process have randomly variable dimensions. A Markov chain Monte Carlo method is used to simulate the posterior distribution for population parameters of interest. The state of the Markov chain Monte Carlo is a random graph, with random dimension and equilibrium distribution equal to the posterior distribution. The aim of the project is to determine if the data is informative of the selection parameter by fitting the model to synthetic data. / Foundation for Research Science and Technology Top Achiever Doctoral Scolarship
|
69 |
Conectividade do grafo aleatório de Erdös-Rényi e uma variante com conexões locaisBedia, Elizbeth Chipa 24 March 2016 (has links)
Submitted by Regina Correa (rehecorrea@gmail.com) on 2016-09-26T13:07:54Z
No. of bitstreams: 1
DissECB.pdf: 1690258 bytes, checksum: 170a56b764c244b7ea84776c96378020 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-27T19:24:19Z (GMT) No. of bitstreams: 1
DissECB.pdf: 1690258 bytes, checksum: 170a56b764c244b7ea84776c96378020 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-27T19:24:24Z (GMT) No. of bitstreams: 1
DissECB.pdf: 1690258 bytes, checksum: 170a56b764c244b7ea84776c96378020 (MD5) / Made available in DSpace on 2016-09-27T19:24:30Z (GMT). No. of bitstreams: 1
DissECB.pdf: 1690258 bytes, checksum: 170a56b764c244b7ea84776c96378020 (MD5)
Previous issue date: 2016-03-24 / Não recebi financiamento / We say that a graph is connected if there is a path edges between any pair of vertices.
Random graph Erd os-R enyi with n vertices is obtained by connecting each pair of vertex with probability pn 2 (0; 1) independently of the others. In this work, we studied
in detail the connectivity threshold in the connection probability pn for random graphs
Erd os-R enyi when the number of vertices n diverges. For this study, we review some basic probabilistic tools (convergence of random variables and methods of the rst and second moment), which will lead to a better understanding of more complex results. In addition, we apply the above concepts for a model with a simple topology, speci cally studied the asymptotic behavior of the probability of non-existence of isolated vertices, and we discussed the connectivity or not of the graph. Finally we show the convergence in distribution of the number of isolated vertices for a Poisson distribution of the studied model. / Dizemos que um grafo e conectado se existe um caminho de arestas entre quaisquer par de vértices. O grafo aleatório de Erd os-R enyi com n vértices e obtido conectando cada par de vértice com probabilidade pn 2 (0; 1), independentemente dos outros. Neste trabalho, estudamos em detalhe o limiar da conectividade na probabilidade de conexão pn para grafos aleat órios Erd os-R enyi quando o n úmero de vértices n diverge. Para este estudo, revisamos algumas ferramentas probabilísticas básicas (convergência de
variáveis aleatórias e Métodos do primeiro e segundo momento), que também irão auxiliar ao melhor entendimento de resultados mais complexos. Além disto, aplicamos os conceitos anteriores para um modelo com uma topologia simples, mais especificamente estudamos o comportamento assintótico da probabilidade de não existência de vértices isolados, e discutimos a conectividade ou não do grafo. Por mostramos a convergência em distribuição do número de vértices isolados para uma Distribuição Poisson do modelo estudado.
|
70 |
Boxicity And Cubicity : A Study On Special Classes Of GraphsMathew, Rogers 01 1900 (has links) (PDF)
Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping f : V (G)→ F such that, An interval graph is an intersection graph of a family of closed intervals on the real line. Interval graphs find application in diverse fields ranging from DNA analysis to VLSI design.
An interval on the real line can be generalized to a k dimensional box or k-box. A k-box B = (R1.R2….Rk) is defined to be the Cartesian product R1 × R2 × …× Rk, where each Ri is a closed interval on the real line. If each Ri is a unit length interval, we call B a k-cube. Thus, an interval is a 1-box and a unit length interval is a 1-cube. A graph G has a k-box representation, if G is an intersection graph of a family of k-boxes in Rk. Similarly, G has a k-cube representation, if G is an intersection graph of a family of k-cubes in Rk. The boxicity of G, denoted by box(G), is the minimum positive integer k such that G has a k-box representation. Similarly, the cubicity of G, denoted by cub(G), is the minimum
positive integer k such that G has a k-cube representation. Thus, interval graphs are the graphs with boxicity equal to 1 and unit interval graphs are the graphs with cubicity equal to 1.
The concepts of boxicity and cubicity were introduced by F.S. Roberts in 1969. Deciding whether the boxicity (or cubicity) of a graph is at most k is NP-complete even for a small positive integer k. Box representation of graphs finds application in niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. Given a low dimensional box representation, some well known NP-hard problems become polynomial time solvable.
Attempts to find efficient box and cube representations for special classes of graphs can be seen in the literature. Scheinerman [6] showed that the boxicity of outerplanar graphs is at most 2. Thomassen [7] proved that the boxicity of planar graphs is bounded from above by 3. Cube representations of special classes of graphs like hypercubes and complete multipartite graphs were investigated in [5, 3, 4]. In this thesis, we present several bounds for boxicity and cubicity of special classes of graphs in terms of other graph parameters. The following are the main results shown in this work.
1. It was shown in [2] that, for a graph G with maximum degree Δ, cub(G) ≤ [4(Δ+ 1) log n]. We show that, for a k-degenerate graph G, cub(G) ≤ (k + 2)[2e log n]. Since k is at most Δ and can be much lower, this clearly is a stronger result. This bound is tight up to a constant factor.
2. For a k-degenerate graph G, we give an efficient deterministic algorithm that runs in O(n2k) time to output an O(k log n) dimensional cube representation.
3. Crossing number of a graph G is the minimum number of crossing pairs of edges, over all drawings of G in the plane. We show that if crossing number of G is t, then box(G) is O(t1/4 log3/4 t). This bound is tight up to a factor of O((log t)1/4 ).
4. We prove that almost all graphs have cubicity O(dav log n), where dav denotes the average degree.
5. Boxicity of a k-leaf power is at most k -1. For every k, there exist k-leaf powers whose boxicity is exactly k - 1. Since leaf powers are a subclass of strongly chordal graphs, this result implies that there exist strongly chordal graphs with arbitrarily high boxicity
6. Otachi et al. [8] conjectured that chordal bipartite graphs (CBGs) have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of CBGs that have unbounded boxicity. We first prove that the bipartite power of a tree (which is a CBG) is a CBG and then show that there exist trees whose bipartite powers have high boxicity. Later in Chapter ??, we prove a more generic result in bipartite powering. We prove that, for every k ≥ 3, the bipartite power of a bipartite, k-chordal graph is bipartite and k-chordal thus implying that CBGs are closed under bipartite powering.
7. Boxicity of a line graph with maximum degree Δ is O(Δ log2 log2 Δ). This is a log2 Δ
log log Δ
factor improvement over the best known upper bound for boxicity of any graph [1]. We also prove a non-trivial lower bound for the boxicity of a d-dimensional hypercube.
|
Page generated in 0.064 seconds