Log in

Relevant bibliographies by topics / Vertex packing polytope

Contents

Journal articles
Dissertations / Theses

Academic literature on the topic 'Vertex packing polytope'

Author: Grafiati

Published: 4 June 2021

Last updated: 12 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Vertex packing polytope.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Vertex packing polytope"

1

Maksimenko, Aleksandr N. "On a family of 0/1-polytopes with an NP-complete criterion for vertex nonadjacency relation." Discrete Mathematics and Applications 29, no. 1 (2019): 7–14. http://dx.doi.org/10.1515/dma-2019-0002.

Full text

Abstract:

Abstract In 1995 T. Matsui considered a special family of 0/1-polytopes with an NP-complete criterion for vertex nonadjacency relation. In 2012 the author demonstrated that all polytopes of this family appear as faces of polytopes associated with the following NP-complete problems: the travelling salesman problem, the 3-satisfiability problem, the knapsack problem, the set covering problem, the partial ordering problem, the cube subgraph problem, and some others. Here it is shown that none of the polytopes of the aforementioned special family (with the exception of the one-dimensional segment)

APA, Harvard, Vancouver, ISO, and other styles

2

Marenco, Javier. "Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope." RAIRO - Operations Research 53, no. 4 (2019): 1267–77. http://dx.doi.org/10.1051/ro/2018085.

Full text

Abstract:

A caterpillar is a connected graph such that the removal of all its vertices with degree 1 results in a path. Given a graph G, a caterpillar-packing of G is a set of vertex-disjoint (not necessarily induced) subgraphs of G such that each subgraph is a caterpillar. In this work we consider the set of caterpillar-packings of a graph, which corresponds to feasible solutions of the 2-schemes strip cutting problem with a sequencing constraint (2-SSCPsc) presented by Rinaldi and Franz (Eur. J. Oper. Res. 183 (2007) 1371–1384). Facet-preserving procedures have been shown to be quite effective at expl

APA, Harvard, Vancouver, ISO, and other styles

3

Steingrímsson, E. "A decomposition of 2-weak vertex-packing polytopes." Discrete & Computational Geometry 12, no. 4 (1994): 465–79. http://dx.doi.org/10.1007/bf02574393.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Changiz Rezaei, Seyed Saeed, and Ehsan Chiniforooshan. "Symmetric Graphs with Respect to Graph Entropy." Electronic Journal of Combinatorics 24, no. 1 (2017). http://dx.doi.org/10.37236/5642.

Full text

Abstract:

Let $F_G(P)$ be a functional defined on the set of all the probability distributions on the vertex set of a graph $G$. We say that $G$ is symmetric with respect to $F_G(P)$ if the uniform distribution on $V(G)$ maximizes $F_G(P)$. Using the combinatorial definition of the entropy of a graph in terms of its vertex packing polytope and the relationship between the graph entropy and fractional chromatic number, we characterize all graphs which are symmetric with respect to graph entropy. We show that a graph is symmetric with respect to graph entropy if and only if its vertex set can be uniformly

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Vertex packing polytope"

1

Changiz, Rezaei Seyed Saeed. "Entropy and Graphs." Thesis, 2014. http://hdl.handle.net/10012/8173.

Full text

Abstract:

The entropy of a graph is a functional depending both on the graph itself and on a probability distribution on its vertex set. This graph functional originated from the problem of source coding in information theory and was introduced by J. K\"{o}rner in 1973. Although the notion of graph entropy has its roots in information theory, it was proved to be closely related to some classical and frequently studied graph theoretic concepts. For example, it provides an equivalent definition for a graph to be perfect and it can also be applied to obtain lower bounds in graph covering problems. In

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!