Separating Cycles in Doubly Toroidal Embeddings

 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     

Numerical schemes for Hamilton-Jacobi equations on unstructured meshes

Summary.  In this paper, a numerical scheme is presented by applying the finite element method to the viscosity equations of the Hamilton-Jacobi equations on unstructured meshes. By improving the finite element scheme, another numerical scheme is constructed. Under certain limitations, the numerical solutions of the two schemes converge to the viscosity solutions of the Hamilton-Jacobi equations. The latter numerical scheme has weaker restrictions than the former scheme for convergence. Numerical examples are provided to test the stability, convergence and sensitivity to different meshes. Received November 5, 2001 / Revised version received March 5, 2002 / Published online October 29, 2002 RID="*" ID="*" Current address: Department of Applied Mathematics, University of Petroleum, Dongying 257062, Shandong, P.R.China; e-mail: xianggui_li@sina.com Mathematics Subject Classification (1991): 65M60     

Effects of uncertainties in the domain on the solution of Dirichlet boundary value problems

Summary. A domain with possibly non-Lipschitz boundary is defined as a limit of monotonically expanding or shrinking domains with Lipschitz boundary. A uniquely solvable Dirichlet boundary value problem (DBVP) is defined on each of the Lipschitz domains and the limit of these solutions is investigated. The limit function also solves a DBVP on the limit domain but the problem can depend on the sequences of domains if the limit domain is unstable with respect to the DBVP. The core of the paper consists in estimates of the difference between the respective solutions of the DBVP on two close domains, one of which is Lipschitz and the other can be unstable. Estimates for starshaped as well as rather general domains are derived. Their numerical evaluation is possible and can be done in different ways. Received October 16, 2001 / Revised version received January 16, 2002 / Published online: April 17, 2002 RID="*" ID="*" The research was funded partially by the National Science Foundation under the grants NSF–Czech Rep. INT-9724783 and NSF DMS-9802367 RID="**" ID="**" Support for Jan Chleboun coming from the Grant Agency of the Czech Republic through grant 201/98/0528 is appreciated     

Locally Well-Dominated and Locally Independent Well-Dominated Graphs

 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.     

On the Classification of Self-Dual Codes over 𝔽5

 In this paper, we give the classification of self-dual 𝔽₅-codes of lengths 14 and 16. Up to equivalence, there are 53 and 535 such codes, respectively. It is also shown that there is no self-dual [18, 9, 8] code over 𝔽₅. Received: June 18, 2001 Final version received: April 9, 2002 RID="*" ID="*" Supported in part by the Academy of Finland under grants 44517 and 100500     

On the structure of rotation-invariant semigroups

 We generalize the notions of Girard algebras and MV-algebras by introducing rotation-invariant semigroups. Based on a geometrical characterization, we present five construction methods which result in rotation-invariant semigroups and in particular, Girard algebras and MV-algebras. We characterize divisibility of MV-algebras, and point out that integrality of Girard algebras follows from their other axioms. Received: 7 January 2002 / Revised version: 4 April 2002 / Published online: 19 December 2002 RID="*" ID="*" Supported by the National Scientific Research Fund Hungary (OTKA F/032782). Mathematics Subject Classification (2000): 20M14, 06F05 Key words or phrases: Residuated lattice – Conjunction for non-classical logics     

Computational complexity of stable partitions with B-preferences

Consider a special stable partition problem in which the player's preferences over sets to which she could belong are identical with her preferences over the most attractive member of a set and in case of indifference the set of smaller cardinality is preferred. If the preferences of all players over other (individual) players are strict, a strongly stable and a stable partition always exists. However, if ties are present, we show that both the existence problems are NP-complete. These results are very similar to what is known for the stable roommates problem. Received: July 2000/Revised: October 2002 RID="*" ID="*"  This work was supported by the Slovak Agency for Science, contract #1/7465/20 “Combinatorial Structures and Complexity of Algorithms”.     

A primal all-integer algorithm based on irreducible solutions

 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     

Some observations on Babu\vs}ka and Brezzi theories

Summary. Some observations are made on abstract error estimates for Galerkin approximations based on Babuška-Brezzi conditions. A basic error estimate due to Babuška is sharpened by means of an identity that for any nontrivial idempotent operator P. Some remarks are also made on the Brezzi's theory for mixed variational problems and their Galerkin approximations. Received March 1, 2000 / Revised version received September 28, 2000 / Published online June 17, 2002 RID="*" ID="*" This work was partially supported by NSF DMS-9706949, NSF ACI-9800244 and NASA NAG2-1236 Correspondence to: J. Xu