Library

feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
Source
Years
Language
  • 1
    Publication Date: 2022-03-11
    Language: English
    Type: article , doc-type:article
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 2
    Publication Date: 2022-03-11
    Description: Conforti, Cornuéjols, Kapoor, and Vusković gave a Hall-type condition for the non-existence of a perfect matching in a balanced hypergraph. We generalize this result to the class of normal hypergraphs.
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 3
    Publication Date: 2022-03-11
    Description: We prove characterizations of the existence of perfect f-matchings in uniform mengerian and perfect hypergraphs. Moreover, we investigate the f-factor problem in balanced hypergraphs. For uniform balanced hypergraphs we prove two existence theorems with purely combinatorial arguments, whereas for non-uniform balanced hypergraphs we show that the f-factor problem is NP-hard.
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 4
    Publication Date: 2022-03-11
    Description: We state purely combinatorial proofs for König- and Hall-type theorems for a wide class of combinatorial optimization problems. Our methods rely on relaxations of the matching and vertex cover problem and, moreover, on the strong coloring properties admitted by bipartite graphs and their generalizations.
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 5
    Publication Date: 2022-03-11
    Description: We prove characterizations of the existence of perfect f-matchings in uniform mengerian and perfect hypergraphs. Moreover, we investigate the f-factor problem in balanced hypergraphs. For uniform balanced hypergraphs we prove two existence theorems with purely combinatorial arguments, whereas for non-uniform balanced hypergraphs we show that the f-factor problem is NP-hard.
    Language: German
    Type: article , doc-type:article
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 6
    Publication Date: 2022-03-11
    Description: We investigate the relation between Hall’s theorem and Kőnig’s theorem in graphs and hypergraphs. In particular, we characterize the graphs satisfying a deficiency version of Hall’s theorem, thereby showing that this class strictly contains all Kőnig–Egerváry graphs. Furthermore, we give a generalization of Hall’s theorem to normal hypergraphs.
    Language: English
    Type: article , doc-type:article
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 7
    Publication Date: 2022-03-11
    Description: The perfect matching polytope, i.e. the convex hull of (incidence vectors of) perfect matchings of a graph is used in many combinatorial algorithms. Kotzig, Lovász and Plummer developed a decomposition theory for graphs with perfect matchings and their corresponding polytopes known as the tight cut decomposition which breaks down every graph into a number of indecomposable graphs, so called bricks. For many properties that are of interest on graphs with perfect matchings, including the description of the perfect matching polytope, it suffices to consider these bricks. A key result by Lovász on the tight cut decomposition is that the list of bricks obtained is the same independent of the choice of tight cuts made during the tight cut decomposition procedure. This implies that finding a tight cut decomposition is polynomial time equivalent to finding a single tight cut. We generalise the notions of a tight cut, a tight cut contraction and a tight cut decomposition to hypergraphs. By providing an example, we show that the outcome of the tight cut decomposition on general hypergraphs is no longer unique. However, we are able to prove that the uniqueness of the tight cut decomposition is preserved on a slight generalisation of uniform hypergraphs. Moreover, we show how the tight cut decomposition leads to a decomposition of the perfect matching polytope of uniformable hypergraphs and that the recognition problem for tight cuts in uniformable hypergraphs is polynomial time solvable.
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 8
    Publication Date: 2022-03-11
    Description: In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst.
    Language: English
    Type: article , doc-type:article
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 9
    Publication Date: 2022-03-11
    Description: In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst.
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 10
    Publication Date: 2022-03-11
    Description: In this thesis we investigate the hyperassignment problem with a special focus on connections to the theory of hypergraphs, in particular balanced and normal hyper- graphs, as well as its relation to the Stable Set Problem. The main point is the investigation of the matching and perfect matching polytope for partitioned hypergraphs. Therefore, valid inequalities, facets, and the dimension of some polytopes are given. Furthermore, we show that the trivial LP-relaxation of the Hyperassignment Problem obtained by relaxing x_i ∈ {0, 1} by 0 ≤ x_i ≤ 1 has an arbitrarily large integrality gap, even after adding all clique inequalities. Whereas the integrality gap of the trivial LP-relaxation of the maximum weight matching problem for partitioned hypergraphs with maximum part size M is at most 2M − 1. Additionally, computational results for small partitioned hypergraphs of part size two are presented. Using symmetry it was possible to calculate all minimal fractional vertices of the fractional perfect matching polytope of partitioned hypergraphs with part size two having at most twelve vertices.
    Language: English
    Type: masterthesis , doc-type:masterThesis
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...