共查询到20条相似文献,搜索用时 125 毫秒
1.
The purpose of this note is to present a relation between directed best approximations of a rational vector and the elements
of the minimal Hilbert basis of certain rational pointed cones. Furthermore, we show that for a special class of these cones
the integer Carathéodory property holds true.
Received May 6, 1998
RID="*"
ID="*" Supported by a "Leibniz Preis" of the German Science Foundation (DFG) awarded to M. Gr?tschel.
RID="†"
ID="†" Supported by a "Gerhard-Hess-Forschungsf?rderpreis" of the German Science Foundation (DFG). 相似文献
2.
In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs,
and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the
independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally
well-dominated graphs.
Received: September 13, 2001 Final version received: May 17, 2002
RID="*"
ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093)
RID="†"
ID="†" Supported by RUTCOR
RID="*"
ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093)
05C75, 05C69
Acknowledgments. The authors thank the referees for valuable suggestions. 相似文献
3.
Dedicated to the memory of Paul Erdős
A graph is called H-free if it contains no induced copy of H. We discuss the following question raised by Erdős and Hajnal. Is it true that for every graph H, there exists an such that any H-free graph with n vertices contains either a complete or an empty subgraph of size at least ? We answer this question in the affirmative for a special class of graphs, and give an equivalent reformulation for tournaments.
In order to prove the equivalence, we establish several Ramsey type results for tournaments.
Received August 22, 1999
RID="*"
ID="*" Supported by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva
Center for Geometry at Tel Aviv University.
RID="†"
ID="†" Supported by NSF grant CR-9732101, PSC-CUNY Research Award 663472, and OTKA-T-020914.
RID="‡"
ID="‡" Supported by TKI grant Stochastics@TUB, and OTKA-T-026203. 相似文献
4.
Dedicated to the memory of Paul Erdős
Let H be a simple graph having no isolated vertices. An (H,k)-vertex-cover of a simple graph G = (V,E) is a collection of subgraphs of G satisfying
1. , for all i = 1, ..., r,
2. ,
3. , for all , and
4. each is in at most k of the . We consider the existence of such vertex covers when H is a complete graph, , in the context of extremal and random graphs.
Received October 31, 1999
RID="*"
ID="*" Supported in part by NSF grant DMS-9627408.
RID="†"
ID="†" Supported in part by NSF grant CCR-9530974.
RID="‡"
ID="‡" Supported in part by OTKA Grants T 030059 and T 29074, FKFP 0607/1999 and by the Bolyai Foundation.
RID="§"
ID="§" Supported in part by NSF grant DMS-9970622. 相似文献
5.
We show that every 4-representative graph embedding in the double torus contains a noncontractible cycle that separates the
surface into two pieces. As a special case, every triangulation of the double torus in which every noncontractible cycle has
length at least 4 has a noncontractible cycle that separates the surface into two pieces.
Received: May 22, 2001 Final version received: August 22, 2002
RID="*"
ID="*" Supported by NSF Grants Numbers DMS-9622780 and DMS-0070613
RID="†"
ID="†" Supported by NSF Grants Numbers DMS-9622780 and DMS-0070430 相似文献
6.
Dedicated to the memory of Paul Erdős
Suppose we have a finite collection of closed convex sets in the plane, (which without loss of generality we can take to be
polygons). Suppose further that among any four of them, some three have non-empty intersection. We show that 13 points are
sufficient to meet every one of the convex sets.
Received October 27, 1999/Revised April 11, 2000
RID="*"
ID="*" Supported by grant OTKA-T-029074.
RID="†"
ID="†" Supported by NSF grant DMS-99-70071, OTKA-T-020914 and OTKA-F-22234. 相似文献
7.
Dedicated to the memory of Paul Erdős
In [9] Thomassen proved that a -connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we
will show that the above statement is still valid for 576k-connected graphs which is essentially best possible.
Received November 17, 1999
RID="*"
ID="*" This work was supported by a post-doctoral DONET grant.
RID="†"
ID="†" This work was supported by an NSF-CNRS collaborative research grant.
RID="‡"
ID="‡" This work was performed while both authors were visiting the LIRMM, Université de Montpellier II, France. 相似文献
8.
Dedicated to the memory of Paul Erdős
We extend a result of J. Alexander and D. Zagier on the Garsia entropy of the Erdős measure. Our investigation heavily relies
on methods from combinatorics on words. Furthermore, we introduce a new singular measure related to the Farey tree.
Received October 7, 1999
RID="†"
ID="†" This author is supported by the START-project Y96-MAT of the Austrian Science Fund
RID="‡"
ID="‡" This author is supported by the Austrian Science Fund (FWF) grant P14200-MAT
RID="*"
ID="*" This author is supported by the Austrian Science Fund (FWF) grant S8307-MAT 相似文献
9.
It is proved that, for any ɛ>0 and n>n
0(ɛ), every set of n points in the plane has at most triples that induce isosceles triangles. (Here e denotes the base of the natural logarithm, so the exponent is roughly 2.136.) This easily implies the best currently known
lower bound, , for the smallest number of distinct distances determined by n points in the plane, due to Solymosi–Cs. Tóth and Tardos.
Received: February, 2002 Final version received: September 15, 2002
RID="*"
ID="*" Supported by NSF grant CCR-00-86013, PSC-CUNY Research Award 63382-00-32, and OTKA-T-032452
RID="†"
ID="†" Supported by OTKA-T-030059 and AKP 2000-78-21 相似文献
10.
Graph Orientations with Edge-connection and Parity Constraints 总被引:2,自引:0,他引:2
Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In an attempt
to understand better their interrelation, we study a problem where both parity and connectivity requirements are imposed.
The main result is a characterization of undirected graphs G = (V,E) having a k-edge-connected T-odd orientation for every subset with |E| + |T| even. (T-odd orientation: the in-degree of v is odd precisely if v is in T.) As a corollary, we obtain that every (2k)-edge-connected graph with |V| + |E| even has a (k-1)-edge-connected orientation in which the in-degree of every node is odd. Along the way, a structural characterization will
be given for digraphs with a root-node s having k edge-disjoint paths from s to every node and k-1 edge-disjoint paths from every node to s.
Received December 14, 1998/Revised January 12, 2001
RID="*"
ID="*" Supported by the Hungarian National Foundation for Scientific Research, OTKA T029772. Part of research was done while
this author was visiting EPFL, Lausanne, June, 1998.
RID="†"
ID="†" Supported by the Hungarian National Foundation for Scientific Research, OTKA T029772 and OTKA T030059. 相似文献
11.
Norbert Sauer 《Combinatorica》2001,21(2):293-308
Dedicated to the memory of Paul Erdős
Erdős, Hajnal and Pósa exhibited in [1] a partition (U,D) of the edges of the Rado graph which is a counterexample to . They also obtained that if every vertex of a graph has either in or in the complement of finite degree then .
We will characterize all graphs so that .
Received October 29, 1999
RID="†"
ID="†" Supported by NSERC of Canada Grant #691325. 相似文献
12.
Bojan Mohar 《Combinatorica》2001,21(3):395-401
It is proved that the decision problem about the existence of an embedding of face-width 3 of a given graph is NP-complete. A similar result is proved for some related decision problems. This solves a problem raised by Neil Robertson.
Received July 6, 1998
RID="*"
ID="*" Supported in part by the Ministry of Science and Technology of Slovenia, Research Project J1–0502–0101–98. 相似文献
13.
Dedicated to the Memory of Paul Erdős
We generalize the multiparty communication model of Chandra, Furst, and Lipton (1983) to functions with b-bit output (b = 1 in the CFL model). We allow the players to receive up to b - 1 bits of information from an all-powerful benevolent Helper who can see all the input. Extending results of Babai, Nisan,
and Szegedy (1992) to this model, we construct families of explicit functions for which bits of communication are required to find the "missing bit", where n is the length of each player's input and k is the number of players. As a consequence we settle the problem of separating the one-way vs. multiround communication complexities
(in the CFL sense) for players, extending a result of Nisan and Wigderson (1991) who demonstrated this separation for k = 3 players. As a by-product we obtain lower bounds for the multiparty complexity (in the CFL sense) of new families of explicit boolean functions (not derivable
from BNS). The proofs exploit the interplay between two concepts of multicolor discrepancy; discrete Fourier analysis is the
basic tool. We also include an unpublished lower bound by A. Wigderson regarding the one-way complexity of the 3-party pointer
jumping function.
Received November 12, 1998
RID="*"
ID="*" Supported in part by NSA grant MSPR-96G-184.
RID="†"
ID="†" Supported in part by an NSF Graduate Fellowship. 相似文献
14.
This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively
substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine
inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how
the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given.
Computational results for a number of hard 0/1 integer programs from the MIPLIB demonstrate the practical power of the method.
Received: April 23, 2001 / Accepted: May 2002
Published online: March 21, 2003
RID="*"
ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.
RID="*"
ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.
RID="*"
ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.
RID="#"
ID="#"Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET
program TMR ERB FMRX-CT98-0202.
Mathematics Subject Classification (1991): 90C10 相似文献
15.
Dedicated to the memory of Paul Erdős
We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method
we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1.
Received December 1, 1999
RID="*"
ID="*" Supported by NSF grant DMS-9704114
RID="**"
ID="**" Supported by KBN grant 2 P03A 032 16 相似文献
16.
Improved Bounds for Acyclic Job Shop Scheduling 总被引:2,自引:0,他引:2
In acyclic job shop scheduling problems there are n jobs and m machines. Each job is composed of a sequence of operations to be performed on different machines. A legal schedule is one
in which within each job, operations are carried out in order, and each machine performs at most one operation in any unit
of time. If D denotes the length of the longest job, and C denotes the number of time units requested by all jobs on the most loaded machine, then clearly lb = max[C,D] is a lower bound on the length of the shortest legal schedule. A celebrated result of Leighton, Maggs, and Rao shows that
if all operations are of unit length, then there always is a legal schedule of length O(lb), independent of n and m. For the case that operations may have different lengths, Shmoys, Stein and Wein showed that there always is a legal schedule
of length , where the notation is used to suppress terms. We improve the upper bound to . We also show that our new upper bound is essentially best possible, by proving the existence of instances of acyclic job
shop scheduling for which the shortest legal schedule is of length . This resolves (negatively) a known open problem of whether the linear upper bound of Leighton, Maggs, and Rao applies to
arbitrary job shop scheduling instances (without the restriction to acyclicity and unit length operations).
Received June 30, 1998
RID="*"
ID="*" Incumbent of the Joseph and Celia Reskin Career Development Chair
RID="†"
ID="†" Research was done while staying at the Weizmann Institute, supported by a scholarship from the Minerva foundation. 相似文献
17.
Say that a function π:n
<ω
→n (henceforth called a predictor) k-constantly predicts a real xn
ω
if for almost all intervals I of length k, there is iI such that x(i)=π(x↾i). We study the k-constant prediction number v
n
const
(k), that is, the size of the least family of predictors needed to k-constantly predict all reals, for different values of n and k, and investigate their relationship.
Received: 27 June 2001 / Revised version: 10 September 2001 /
Published online: 10 October 2002
RID="*"
ID="*" Supported by Grant–in–Aid for Scientific Research (C)(2)12640124, Japan Society for the Promotion of Science
RID="†"
ID="†" Supported by The Israel Science Foundation founded by the Israel Academy of Sciences and Humanities. Publication 762 相似文献
18.
Sung Y. Song 《Graphs and Combinatorics》2002,18(3):655-665
Fusion relations between the association schemes obtained by direct product and wreath product are established via a study
of their matrix representations. The character table of the scheme obtained by the wreath product is described and some algebraic
properties of the products are derived.
Received: May 7, 1999 Final version received: September 24, 1999
RID="*"
ID="*" 1991 Mathematics Subject Classification. Primary 05E30; Secondary 05B99
RID="*"
ID="*" Supported in part by Com 2MaC-KOSEF, POSTECH, Korea
Acknowledgments. The author is indebted to an anonymous referee who provided the complete proof of Theorem 4.2. 相似文献
19.
Dedicated to the memory of Paul Erdős
A graph is called -free if it contains no cycle of length four as an induced subgraph. We prove that if a -free graph has n vertices and at least edges then it has a complete subgraph of vertices, where depends only on . We also give estimates on and show that a similar result does not hold for H-free graphs––unless H is an induced subgraph of . The best value of is determined for chordal graphs.
Received October 25, 1999
RID="*"
ID="*" Supported by OTKA grant T029074.
RID="**"
ID="**" Supported by TKI grant stochastics@TUB and by OTKA grant T026203. 相似文献
20.
Oleg Pikhurko 《Combinatorica》2001,21(3):403-412
Let be the star with n edges, be the triangle, and be the family of odd cycles. We establish the following bounds on the corresponding size Ramsey numbers.
The upper (constructive) bound disproves a conjecture of Erdős.
Also we show that provided is an odd cycle of length o(n) or is a 3-chromatic graph of order o(log n).
Received May 28, 1999
RID="*"
ID="*" Supported by an External Research Studentship, Trinity College, Cambridge, UK. 相似文献