14140438
On the Genus of a Random Graph
Let p = p(n) be a function of n with 0 1 we were unable to compute this function. © 1995 Wiley Periodicals, Inc.
33726107
A menger-like property of tree-width: The finite case
The notion of tree-width was introduced by Robertson and Symour. A graph has tree-width ≦ w if it admits a tree-decomposition of tree-width ≦ w. We prove here that if G is finite and has tree-width ≦ w then it admits a tree-decomposition of tree-width ≦ w which satisfies a certain Menger-like condition. This result will be used in a future paper on well-quasi-ordering infinite graphs of bounded tree-width.
18561897
Excluding infinite minors
Let ? be an infinite cardinal, and let H be either a complete graph with ? vertices, or a tree in which every vertex has valency ?. What can we say about graphs G which (i) have no minor isomorphic to H, or (ii) contain no subgraph which is a subdivision of H?These four questions are answered for each infinite cardinal ?. In each case we find that there corresponds a necessary and sufficient structural condition (or, in some cases, several equivalent conditions) for G not to contain H in the appropriate way. We survey these results and a number of related theorems.
10511288
Clique Minors in Graphs and Their Complements
A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t?1 be an integer, and let G be a graph on n vertices with no minor isomorphic to Kt+1. Kostochka conjectures that there exists a constant c=c(t) independent of G such that the complement of G has a minor isomorphic to Ks, where s=?12(1+1/t)n?c?. We prove that Kostochka's conjecture is equivalent to the conjecture of Duchet and Meyniel that every graph with no minor isomorphic to Kt+1 has an independent set of size at least n/t. We deduce that Kostochka's conjecture holds for all integers t?5, and that a weaker form with s replaced by s?=?12(1+1/(2t))n?c? holds for all integers t?1.
2783736
List Edge-Colorings of Series-Parallel Graphs
It is proved that for every integer $k\ge3$, for every (simple) series-parallel graph $G$ with maximum degree at most $k$, and for every collection $(L(e):e\in E(G))$ of sets, each of size at least $k$, there exists a proper edge-coloring of $G$ such that for every edge $e\in E(G)$, the color of $e$ belongs to $L(e)$.
206570580
Sachs' Linkless Embedding Conjecture
Abstract We prove Sachs′ conjecture that a graph can be embedded in 3-space so that it contains no non-trivial link (in the sense of knot theory) if and only if it contains as a minor none of the seven graphs obtainable from K 6 by Y − Δ and Δ − Y exchanges. We also show the following: (i) A graph admits such a "linkless" embedding if and only if it admits a "panelled" embedding, one such that every circuit of the graph bounds a disc disjoint from the remainder of the graph. This was a conjecture of Bohme. (ii) An embedding is panelled if and only if for every subgraph, its complement in 3-space has free fundamental group. This extends a theorem of Scharlemann and Thompson, who proved it for planar graphs. (iii) If two panelled embeddings of the same graph are "different," that is, are not related by an orientation-preserving homeomorphism of the 3-space, then there is a subgraph which is a subdivision of K 5 or K 3, 3 such that the two induced embeddings of this subgraph are still different.
14857147
An economic analysis of the self commitment of thermal units
Given the load profile of an electricity market and the capabilities of the set of generators supplying power to that market, it is likely that at any given point in time, available supply will exceed demand. If only a subset of generators is required, some method is required to commit and de-commit generators. In the past, system operators have employed a centralized method of unit commitment. Deregulation of the electricity industry throws doubt on the continued suitability of this method due to fairness issues and availability of accurate cost data. This paper examines the performance of decentralized unit commitment, where dispatch of generators is determined by offer curves submitted into a spot market by power producers.
17884360
Experimental results for single period auctions
The objective of the paper is to present experimental results for testing the performance of different auction mechanisms related to the introduction of competitive markets for the generation of electricity. The research is based on the concept of smart markets introduced by Vernon Smith (K.A. McCabe et al., 1991) and a simulation model (PowerWeb) of a realistic bulk power system. There are unique physical aspects associated with the supply of electricity (e.g. required instantaneous matching of supply and demand, unintended congestion of parallel transmission routes and maintenance of system stability in response to disturbances). As a result, traditional theories of efficient markets and auction structures developed for other commodities may not be efficient if applied without alteration to markets for electricity. Conversely, current utility rules of operation developed for a centrally planned regime may not be appropriate in a competitive environment. The research does not address the issues of multiperiod operations (unit commitment) and multidimensional markets (ancillary services), and considers only real power in a single time period. The main objective is to test three alternative auction mechanisms when market power is a potential problem. This situation occurs when limits on transmission lines are binding to form a load pocket in which demand is met by a few (in this case two) generators.
2943319
Thermal unit commitment including optimal AC power flow constraints
The authors propose a new algorithm for unit commitment that employs a Lagrange relaxation technique with a new augmentation of the Lagrangian. The new augmentation involves a duplication of variables that allows relaxation of the coupling between generator time-spanning constraints and system-wide instantaneous constraints. This framework allows the possibility of committing units that are required for the VArs that they can produce, as well as for their real power. Furthermore, although the algorithm is very CPU-intensive, the separation structure of the Lagrangian allows its implementation in parallel computers. Their work builds upon that of Batut and Renaud (1992), as well as that of Baldick (1995).
2733176
The pervasiveness of evolution in GRUMPS software
This paper describes the evolution of the design and implementation of a distributed run-time system that itself is designed to support the evolution of the topology and implementation of an executing, distributed system. The three different versions of the run-time architecture that have been designed and implemented are presented, together with how each architecture addresses the problems of topological and functional evolution. In addition, the reasons for the rapid evolution of the design and implementation of the architecture are also described.From the lessons learned in both evolving the design of the architecture and in trying to provide a run-time system that can support run-time evolution, this paper discusses two generally applicable observations: evolution happens all the time, and it is not possible to anticipate how systems will evolve as designs; and large, run-time systems do not follow a predictable path. In addition to this, rapid prototyping has proved to be extremely useful in the production of the three architectures; this kind of prototyping has been made much easier by designing the core set of Java abstractions in terms of interfaces; and building an architecture that allows as many decisions as possible to be made at run-time which has produced a support system that is more responsive to the user as well as the distributed environment in which it is executing.
33773
An Agent-Based Optimal Bidding Function
Problems such as price volatility have been observed in electric power markets. Demand-side participation is often offered as a potential solution by promising to increase market efficiency when hockey-stick type offer curves are present. However, individual end-consumer will surely value electricity differently, which makes demand-side participation as a group and at a bus difficult. In this paper demand is categorized into two groups: one that highly values reliability and the other that does not. The two types are modeled separately and a new optimal bidding function is developed and tested based on this model.