共查询到20条相似文献,搜索用时 71 毫秒
1.
We give a state-of-the-art survey of the thickness of a graph from both a theoretical and a practical point of view. After
summarizing the relevant results concerning this topological invariant of a graph, we deal with practical computation of the
thickness. We present some modifications of a basic heuristic and investigate their usefulness for evaluating the thickness
and determining a decomposition of a graph in planar subgraphs. 相似文献
2.
Let G be an edge-colored graph. The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic
trees to cover the all vertices of G. In the authors’ previous work, it has been proved that the problem is NP-complete and there does not exist any constant
factor approximation algorithm for it unless P = NP. In this paper the authors show that for any fixed integer r ≥ 5, if the edges of a graph G are colored by r colors, called an r-edge-colored graph, the problem remains NP-complete. Similar result holds for the monochromatic path (cycle) partition problem.
Therefore, to find some classes of interesting graphs for which the problem can be solved in polynomial time seems interesting.
A linear time algorithm for the monochromatic path partition problem for edge-colored trees is given.
Supported by the National Natural Science Foundation of China, PCSIRT and the “973” Program. 相似文献
3.
4.
A.D. Scott 《Graphs and Combinatorics》2001,17(3):539-553
Gallai proved that the vertex set of any graph can be partitioned into two sets, each inducing a subgraph with all degrees
even. We prove that every connected graph of even order has a vertex partition into sets inducing subgraphs with all degrees
odd, and give bounds for the number of sets of this type required for vertex partitions and vertex covers. We also give results
on the partitioning and covering problems for random graphs.
Received: October 5, 1998?Final version received: October 20, 2000 相似文献
5.
We study how the average performance of a system degrades as the load nears its peak capacity. We restrict our attention to
the performance measures of average sojourn time and the large deviation rates of buffer overflow probabilities. We first
show that for certain queueing systems, the average sojourn time of requests depends much more weakly on the load ρ than the
commonly observed 1/(1−ρ) dependence for most queueing policies. For example, we show that for an M/G/1 system under the preemptive
Shortest Job First (pSJF) policy, the average sojourn time varies as log (1/(1−ρ)) with load for a certain class of distributions.
We observe that such results hold even for more restricted policies. We give some examples of non-preemptive policies and
policies that do not use the knowledge of job sizes while scheduling, where the dependence of average sojourn time on load
is significantly better than 1/(1−ρ). Similar results hold even for very simple non-preemptive threshold based policies that
partition all the jobs into two job classes based on a fixed threshold and do FIFO within each class. Finally we study the
large deviations rate of the queue length under a simple dedicated partition-based policy. 相似文献
6.
We generalize Dijkstra's algorithm for finding shortest paths in digraphs with non-negative integral edge lengths. Instead of labeling individual vertices we label subgraphs which partition the given graph. We can achieve much better running times if the number of involved subgraphs is small compared to the order of the original graph and the shortest path problems restricted to these subgraphs is computationally easy.As an application we consider the VLSI routing problem, where we need to find millions of shortest paths in partial grid graphs with billions of vertices. Here, our algorithm can be applied twice, once in a coarse abstraction (where the labeled subgraphs are rectangles), and once in a detailed model (where the labeled subgraphs are intervals). Using the result of the first algorithm to speed up the second one via goal-oriented techniques leads to considerably reduced running time. We illustrate this with a state-of-the-art routing tool on leading-edge industrial chips. 相似文献
7.
We start by introducing a Čech homology with compact supports which we then use in order to construct an infinite-dimensional
homology theory. Next we show that under appropriate conditions on the nonlinearity there exists a ground state solution for
a semilinear Schr?dinger equation with strongly indefinite linear part. To this solution there corresponds a nontrivial critical
group, defined in terms of the infinite-dimensional homology mentioned above. Finally, we employ this fact in order to construct
solutions of multibump type. Although our main purpose is to survey certain homological methods in critical point theory,
we also include some new results.
Dedicated to Felix Browder on the occasion of his 80th birthday 相似文献
8.
Two questions are considered, namely (i) How many colors are needed for a coloring of the n-cube without monochromatic quadrangles or hexagons? We show that four colors suffice and thereby settle a problem of Erdös. (ii) Which vertex-transitive induced subgraphs does a hypercube have? An interesting graph has come up in this context: If we delete a Hamming code from the 7-cube, the resulting graph is 6-regular, vertex-transitive and its edges can be two-colored such that the two monochromatic subgraphs are isomorphic, cubic, edge-transitive, nonvertex-transitive graphs of girth 10. 相似文献
9.
We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear
integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block
of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For
the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating
the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that
seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the
results of some computational experiments.
Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002
Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral
bound – Fischer's inequality – branch-and-bound – dynamic programming
Mathematics Subject Classification (2000): 52B12, 90C10
Send offprint requests to: Jon Lee
Correspondence to: Jon Lee 相似文献
10.
Alberto Del Pia 《4OR: A Quarterly Journal of Operations Research》2010,8(1):105-108
We survey the main results of the PhD Thesis presented by the author in January 2009 at the University of Padova. This work
was supervised by Giacomo Zambelli. The thesis is written in English and is available from the author upon request. In this
work we consider the Edmonds–Johnson property and we survey some related results. Next we present our contributions, that
consist into two classes of matrices with the Edmonds–Johnson property. Our work generalizes previous results by Edmonds and
Johnson (Math Program 5:88–124, 1973), and by Conforti et al. (in Integer programming and combinatorial optimization, proceedings
of IPCO 2007). Both our results are special cases of a conjecture introduced by Gerards and Schrijver. 相似文献
11.
Flavia Bonomo Guillermo Durán Min Chih Lin Jayme L Szwarcfiter 《Mathematical Programming》2006,105(2-3):233-250
Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs,
and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs
and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs.
Two of them are characterized by 0–1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial
time combinatorial algorithms for the problems of stable set, clique-independent set and clique-transversal for one of these
subclasses of balanced graphs. Finally, we analyse the behavior of balanced graphs and these four subclasses under the clique
graph operator.
Received: April, 2004 相似文献
12.
We connect different results about irreducible components of the Springer fibers of type A. Firstly, we show a relation between the Spaltenstein partition of the fibers and a total order
on the set of standard Young tableaux. Next, using a result of Steinberg, we connect a work of the first author to the Robinson–Schensted
map. We also perform the Spaltenstein study of the relative position of the Springer fibers and
-fibrations of the flag manifold. This leads us to consider the adjacency relation on the set of standard Young tableaux
and to define oriented and labeled graphs with the standard Young tableaux as vertices. Using this adjacency relation, we
describe some smooth irreducible components of the Springer fibers. Finally, we show that these graphs can be identified with
some full subgraphs of the Bruhat graph. 相似文献
13.
Mean field games 总被引:1,自引:0,他引:1
We survey here some recent studies concerning what we call mean-field models by analogy with Statistical Mechanics and Physics.
More precisely, we present three examples of our mean-field approach to modelling in Economics and Finance (or other related
subjects...). Roughly speaking, we are concerned with situations that involve a very large number of “rational players” with
a limited information (or visibility) on the “game”. Each player chooses his optimal strategy in view of the global (or macroscopic)
informations that are available to him and that result from the actions of all players. In the three examples we mention here,
we derive a mean-field problem which consists in nonlinear differential equations. These equations are of a new type and our
main goal here is to study them and establish their links with various fields of Analysis. We show in particular that these
nonlinear problems are essentially well-posed problems i.e., have unique solutions. In addition, we give various limiting
cases, examples and possible extensions. And we mention many open problems.
This article is based on the 1st Takagi Lectures that the second author delivered at Research Institue for Mathematical Sciences,
Kyoto University on November 25 and 26, 2006.
Jean-Michel Lasry and Pierre-Louis Lions: work partially supported by the chair “Finance and sustainable development” 相似文献
14.
We develop general methods to obtain fast (polynomial time) estimates of the cardinality of a combinatorially defined set
via solving some randomly generated optimization problems on the set. Examples include enumeration of perfect matchings in
a graph, linearly independent subsets of a set of vectors and colored spanning subgraphs of a graph. Geometrically, we estimate
the cardinality of a subset of the Boolean cube via the average distance from a point in the cube to the subset with respect
to some distance function. We derive asymptotically sharp cardinality bounds in the case of the Hamming distance and show
that for small subsets a suitably defined “randomized” Hamming distance allows one to get tighter estimates of the cardinality.
Submitted: June 2000, Revised version: January 2001. 相似文献
15.
Dmitry N. Kozlov 《Israel Journal of Mathematics》2002,132(1):189-206
In this paper we study the topology of the strata, indexed by number partitions λ, in the natural stratification of the space
of monic hyperbolic polynomials of degreen. We prove stabilization theorems for removing an independent block or an independent relation in λ. We also prove contractibility
of the ‘one-point compactifications of the strata indexed by a large class of number partitions, including λ=(k
m
, 1
r
), form≥2. Furthermore, we study the maps between the homology groups of the strata, induced by imposing additional relations (resonances)
on the number partition λ, or by merging some of the blocks of λ. 相似文献
16.
We show the existence of rainbow perfect matchings in μn‐bounded edge colorings of Dirac bipartite graphs, for a sufficiently small μ > 0. As an application of our results, we obtain several results on the existence of rainbow k‐factors in Dirac graphs and rainbow spanning subgraphs of bounded maximum degree on graphs with large minimum degree. 相似文献
17.
Tnaz Ekim Pavol Hell Juraj Stacho Dominique de Werra 《Discrete Applied Mathematics》2008,156(13):2469-2479
Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, the existence of such a partition can be characterized by finitely many forbidden subgraphs, and hence tested in polynomial time. In this paper we address the question of polarity of chordal graphs, arguing that this is in essence a question of colourability, and hence chordal graphs are a natural restriction. We observe that there is no finite forbidden subgraph characterization of polarity in chordal graphs; nevertheless we present a polynomial time algorithm for polarity of chordal graphs. We focus on a special case of polarity (called monopolarity) which turns out to be the central concept for our algorithms. For the case of monopolar graphs, we illustrate the structure of all minimal obstructions; it turns out that they can all be described by a certain graph grammar, permitting our monopolarity algorithm to be cast as a certifying algorithm. 相似文献
18.
We give a survey of some general results on graph limits associated to hereditary classes of graphs. As examples, we consider some classes defined by forbidden subgraphs and some classes of intersection graphs, including triangle-free graphs, chordal graphs, cographs, interval graphs, unit interval graphs, threshold graphs, and line graphs. 相似文献
19.
In this paper we will show that every simplexX with circumradiusϱ satisfies the following geometric partition property, which proves a conjecture from [FR90].
For every positive realδ there exists a positive realσ such that everygc-colouring of then-dimensional sphere of radiusϱ+δ withχ≤(1+σ)
n
results in a monochromatic copy ofX. 相似文献
20.
The Linear Arboricity of Series-Parallel Graphs 总被引:8,自引:0,他引:8
Jianliang Wu 《Graphs and Combinatorics》2000,16(3):367-372
The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. A graph is called series-parallel if it contains no subgraphs homeomorphic to K
4. In this paper, we prove that for any series-parallel graph G having Δ (G)≥3. Since an outerplanar graph is a series-parallel graph, this is also true for any outerplanar graph.
Received: August 20, 1997 Revised: March 12, 1999 相似文献