Change search
Refine search result
1 - 11 of 11
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Asratian, Armen S.
    et al.
    Luleå University of Technology.
    Denley, Tristan M.J.
    University of Mississippi.
    Häggkvist, Roland
    University of Umeå.
    Bipartite graphs and their applications1998Book (Other academic)
    Abstract [en]

    Bipartite graphs constitute one of the most intensively investigated classes of graphs, yet this book appears to be the first devoted entirely to their study. It provides a comprehensive introduction to the subject, with considerable emphasis on applications. In fact most of the chapters have at least one section devoted to applications in other fields of study. Although the grammar is sometimes in need of repair (for example, sentences are occasionally spliced together with commas), the book is clearly written. Many of the exercises are quite challenging. As the basic concepts of graph theory are carefully explained in Chapter 1, this book can be warmly recommended not only to experts but also to those seeking an accesible yet rigorous introduction to bipartite graphs, or indeed to graphs in general.

  • 2.
    Asratian, Armen S.
    et al.
    Luleå tekniska universitet.
    Kuzjurin, N. N..
    Institute of System Programming, Russian Academy of Sciences.
    New class of 0-1 integer programs with tight approximation via linear relaxations2001In: Mathematical Methods of Operations Research, ISSN 1432-2994, E-ISSN 1432-5217, Vol. 53, no 3, p. 363-370Article in journal (Refereed)
    Abstract [en]

    We consider the problem of estimating optima of integer programs { max cx | Axhb,0hxh1, x m integral} where b>0, cS0 are rational vectors and A is an arbitrary rational m 2n matrix. Using randomized rounding we find an efficiently verifiable sufficient condition for optima of such integer programs to be close to the optima q of their linear relaxations. We show that our condition guarantees that for any constant )>0 and sufficiently large n there exists a feasible integral solution z such that qS czS(1m))q.

  • 3.
    Asratian, Armen S.
    et al.
    Luleå tekniska universitet.
    Kuzjurin, N. N.
    Institute of System Programming, Russian Academy of Sciences.
    On the number of nearly perfect matchings in almost regular uniform hypergraphs1999In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 207, no 1, p. 1-8Article in journal (Refereed)
    Abstract [en]

    Strengthening the result of R dl and Frankl (Europ. J. Combin 6 (1985) 317-326), Pippenger proved the theorem stating the existence of a nearly perfect matching in almost regular uniform hypergraph satisfying some conditions (see J. Combin. Theory A 51 (1989) 24-42). Grable announced in J. Combin. Designs 4 (4) (1996) 255-273 that such hypergraphs have exponentially many nearly perfect matchings. This generalizes the result and the proof in Combinatorica 11 (3) (1991) 207-218 which is based on the R dl Nibble algorithm (European J. Combin. 5 (1985) 69-78). In this paper, we present a simple proof of Grable's extension of Pippenger's theorem. Our proof is based on a comparison of upper and lower bounds of the probability for a random subgraph to have a nearly perfect matching. We use the Lovasz Local Lemma to obtain the desired lower bound of this probability.

  • 4. Asratian, Armen S.
    et al.
    Kuzjurin, N. N.
    Two sensitivity theorems in fuzzy integer programming2000Report (Other academic)
    Abstract [en]

    We consider the problem of estimating optima of covering integer linear programs with 0-1 variables under the following conditions: we do not know exact values of elements in the constraint matrix A but we know what elements of A are zero and what are nonzero, and also know minimal and maximal values of nonzero elements. We find bounds for variation of the optima of such programs in worst and average cases. We also find some conditions guaranteeing that the variation of the optimum of such programs in the average case is close to 1 as the number of variables tends to infinity. This means that the values of nonzero elements in A can vary in sufficiently large interval do not affecting significantly on the value of the optimum of integer program.

  • 5.
    Asratian, Armen S
    et al.
    Luleå tekniska universitet.
    Kuzjurin, N.N.
    Institute of System Programming, Russian Academy of Sciences.
    On the number of nearly perfect matchings in almost regular uniform hypergraphs2002In: Paul Erdos and his mathematics / [ed] Gábor Halász, Berlin: János Bolyai Mathematical Society , 2002Conference paper (Refereed)
  • 6.
    Asratian, Armen S.
    et al.
    Luleå tekniska universitet.
    Werra, D. de
    École Polytechnique Fédérale de Lausanne.
    A generalized class-teacher model for some timetabling problems2002In: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 143, no 3, p. 531-542Article in journal (Refereed)
    Abstract [en]

    We consider a theoretical model which extends the basic "class-teacher model" of timetabling and which corresponds to some situations which occur frequently in the basic training programs of universities and schools. We are given m teachers T1, ..., Tm and n classes C1, ..., Cn. The set of classes is partitioned into p disjoint subsets G1, ..., Gp in such a way that in addition to the lectures given by one teacher to one class, there are some lectures given by one teacher to the students of all classes in group Gl, 1 ≤ l ≤ p. Such lectures will be called group-lectures. The number alj of one hour group-lectures which teacher Tj must deliver to group Gl and the number bij of one hour class-teaching which Tj must give to class Ci are given. Is there a timetable of t hours (or length t), so that each class Ci and each group Gl receive all their lectures, but no student is scheduled to be taught by more than one teacher in each hour, and no teacher must teach to more than one group or class in each hour? We show that this problem is NP-complete and find some sufficient conditions for the existence of a timetable of length t. We also describe an algorithm for constructing a timetable corresponding to the requirement matrices A = (alj) and B = (bij) and show that under a natural assumption on A and B this algorithm finds a timetable within 7/6 of the optimum length

  • 7.
    Asratian, Armen.S.
    Luleå University of Technology.
    Short solution of Kotzig's problem for bipartite graphs1998In: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 74, no 2, p. 160-168Article in journal (Refereed)
    Abstract [en]

    In 1975, A. Kotzig posed the following problem: LetGbe at-regular graph which has a proper edget-coloring,t4. Is it possible to obtain, from one proper edget-coloring ofG, any other proper edge t-coloring of G using only transformations of 2-colored and 3-colored subgraphs such that the intermediate colorings are also proper? The author and A. N. Mirumian proved that it is possible ifGis a bipartite graph. We give here a short proof of this result

  • 8.
    Asratian, A.S.
    Luleå University of Technology.
    Some results on an edge coloring problem of Folkman and Fulkerson2000In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 223, no 1-3, p. 13-25Article in journal (Refereed)
    Abstract [en]

    In 1968, Folkman and Fulkerson posed the following problem: Let G be a graph and let (n1,...,nt) be a sequence of positive integers. Does there exist a proper edge coloring of G with colors 1,2,...,t such that precisely ni edges receive color i, for each i=1,...,t? If such a coloring exists then the sequence (n1,...,nt) is called color-feasible for G. Some sufficient conditions for a sequence to be color-feasible for a bipartite graph where found by Folkman and Fulkerson, and de Werra. In this paper we give a generalization of their results for bipartite graphs. Furthermore, we find a set of color-feasible sequences for an arbitrary simple graph. In particular, we describe the set of all sequences which are color-feasible for a connected simple graph G with Δ(G)3, where every pair of vertices of degree at least 3 are non-adjacent.

  • 9.
    Asratian, A.S.
    et al.
    Luleå University of Technology.
    Kuzjurin, N.N.
    Institute of System Programming, Russian Academy of Sciences.
    On the number of partial Steiner systems2000In: Journal of combinatorial designs (Print), ISSN 1063-8539, E-ISSN 1520-6610, Vol. 8, no 5, p. 347-352Article in journal (Refereed)
    Abstract [en]

    We give a simple proof of the result of Grable on the asymptotics of the number of partial Steiner systems S(t,k,m).

  • 10. Asratian, A.S.
    et al.
    Oksimets, N.
    Department of Mathematics, University of Umeå.
    Graphs with Hamiltonian balls1998In: The Australasian Journal of Combinatorics, ISSN 1034-4942, Vol. 17, p. 185-198Article in journal (Refereed)
    Download full text (pdf)
    fulltext
  • 11.
    Werra, D. de
    et al.
    École Polytechnique Fédérale de Lausanne.
    Asratian, Armen S.
    Durand, Sylvain
    Laboratoire d'Informatique d'Avignon.
    Complexity of some special types of timetabling problems2002In: Journal of Scheduling, ISSN 1094-6136, E-ISSN 1099-1425, Vol. 5, no 2, p. 171-183Article in journal (Refereed)
    Abstract [en]

    Starting from the simple class-teacher model of timetabling (where timetables correspond to edgecolorings of a bipartite multigraph), we consider an extension defined as follows: we assume that the set of classes is partitioned into groups. In addition to the teachers giving lectures to individual classes, we have a collection of teachers who give all their lectures to groups of classes. We show that when there is one such teacher giving lectures to three groups of classes, the problem is NP-complete. We also examine the case where there are at most two groups of classes and we give a polynomial procedure based on network flows to find a timetable using at most t periods.

1 - 11 of 11
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf