The complexity of facets (and some facets of complexity) (Q1061485): Difference between revisions

Latest revision as of 17:30, 14 June 2024

scientific article

Language	Label	Description	Also known as
English	The complexity of facets (and some facets of complexity)	scientific article

Statements

instance of

scholarly article

0 references

title

The complexity of facets (and some facets of complexity) (English)

0 references

published in

Journal of Computer and System Sciences

0 references

publication date

1984

0 references

review text

The authors introduce a certain complexity class \(D^ P\) connected with combinatorial optimization problems and in particular with the facets of polytopes. \(D^ P\) is the class of all languages that are the intersection of a language in NP and a language in coNP.

0 references

zbMATH Keywords

complexity class

0 references

combinatorial optimization

0 references

facets of polytopes

0 references

NP

0 references

coNP

0 references

author

Christos H. Papadimitriou

0 references

Mihalis Yannakakis

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0022-0000(84)90068-0

0 references

cites work

Facets of the knapsack polytope

0 references

Q3892882

0 references

Q3941433

0 references

Edmonds polytopes and weakly hamiltonian graphs

0 references

On certain polytopes associated with graphs

0 references

Q3844775

0 references

Solution of a Large-Scale Traveling-Salesman Problem

0 references

New families of hypohamiltonian graphs

0 references

Q4198056

0 references

The edge inducibility of graphs

0 references

On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and Facets

0 references

On the symmetric travelling salesman problem II: Lifting theorems and facets

0 references

Parallel concepts in graph theory

0 references

Q4142699

0 references

The 3-Irreducible Partially Ordered Sets

0 references

Q3050157

0 references

Optimization problems and the polynomial hierarchy

0 references

An Infinite Class of Hypohamiltonian Graphs

0 references

Properties of vertex packing and independence system polyhedra

0 references

On the facial structure of set packing polyhedra

0 references

Q4182528

0 references

Q4739657

0 references

Hypohamiltonian and hypotraceable graphs

0 references

Characterization problems for graphs, partially ordered sets, lattices, and families of sets

0 references

Q3684168

0 references

Further facet generating procedures for vertex packing polytopes

0 references

The Complexity of the Partial Order Dimension Problem

0 references

Identifiers

zbMATH Open document ID

0571.68028

0 references

DOI

10.1016/0022-0000(84)90068-0

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1061485

@@ Property / author @@
+Christos H. Papadimitriou
@@ Property / author: Christos H. Papadimitriou / rank @@
+Normal rank
@@ Property / author @@
+Mihalis Yannakakis
@@ Property / author: Mihalis Yannakakis / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0022-0000(84)90068-0
+Normal rank
@@ Property / OpenAlex ID @@
+W2093454413
@@ Property / OpenAlex ID: W2093454413 / rank @@
+Normal rank
@@ Property / cites work @@
+Facets of the knapsack polytope
@@ Property / cites work: Facets of the knapsack polytope / rank @@
+Normal rank
@@ Property / cites work @@
+Q3892882
@@ Property / cites work: Q3892882 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3941433
@@ Property / cites work: Q3941433 / rank @@
+Normal rank
@@ Property / cites work @@
+Edmonds polytopes and weakly hamiltonian graphs
@@ Property / cites work: Edmonds polytopes and weakly hamiltonian graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On certain polytopes associated with graphs
@@ Property / cites work: On certain polytopes associated with graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3844775
@@ Property / cites work: Q3844775 / rank @@
+Normal rank
@@ Property / cites work @@
+Solution of a Large-Scale Traveling-Salesman Problem
+Normal rank
@@ Property / cites work @@
+New families of hypohamiltonian graphs
@@ Property / cites work: New families of hypohamiltonian graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+The edge inducibility of graphs
@@ Property / cites work: The edge inducibility of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and Facets
+Normal rank
@@ Property / cites work @@
+On the symmetric travelling salesman problem II: Lifting theorems and facets
+Normal rank
@@ Property / cites work @@
+Parallel concepts in graph theory
@@ Property / cites work: Parallel concepts in graph theory / rank @@
+Normal rank
@@ Property / cites work @@
+Q4142699
@@ Property / cites work: Q4142699 / rank @@
+Normal rank
@@ Property / cites work @@
+The 3-Irreducible Partially Ordered Sets
@@ Property / cites work: The 3-Irreducible Partially Ordered Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Q3050157
@@ Property / cites work: Q3050157 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimization problems and the polynomial hierarchy
+Normal rank
@@ Property / cites work @@
+An Infinite Class of Hypohamiltonian Graphs
@@ Property / cites work: An Infinite Class of Hypohamiltonian Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Properties of vertex packing and independence system polyhedra
+Normal rank
@@ Property / cites work @@
+On the facial structure of set packing polyhedra
@@ Property / cites work: On the facial structure of set packing polyhedra / rank @@
+Normal rank
@@ Property / cites work @@
+Q4182528
@@ Property / cites work: Q4182528 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4739657
@@ Property / cites work: Q4739657 / rank @@
+Normal rank
@@ Property / cites work @@
+Hypohamiltonian and hypotraceable graphs
@@ Property / cites work: Hypohamiltonian and hypotraceable graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Characterization problems for graphs, partially ordered sets, lattices, and families of sets
+Normal rank
@@ Property / cites work @@
+Q3684168
@@ Property / cites work: Q3684168 / rank @@
+Normal rank
@@ Property / cites work @@
+Further facet generating procedures for vertex packing polytopes
+Normal rank
@@ Property / cites work @@
+The Complexity of the Partial Order Dimension Problem
+Normal rank