On the complexity of some problems related to graph extensions

DOI10.1134/S0001434610110015MaRDI QIDQ650325zbMATH OpenOpenAlexFDO

Authors M. B. Abrosimov

Publication date 25 November 2011

Published in Mathematical Notes (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0001434610110015

zbMATH Keywords

\(NP\) problem\(NP\)-complete problemexact \(k\)-extensionextension of graphsfault toleranceirreducible \(k\)-extensionminimal \(k\)-extensionvertex and edge \(k\)-extension

Mathematics Subject Classification ID

Vertex degrees (05C07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 7300406
• scientific article; zbMATH DE number 1302031
• On a certain complexity estimate in graph theory
• Extension of some edge graph problems: standard and parameterized complexity
• scientific article; zbMATH DE number 3874609
• scientific article; zbMATH DE number 3874608
• scientific article; zbMATH DE number 4162940
• On some extremal problems in graph theory
• Extension of some edge graph problems: standard, parameterized and approximation complexity
• scientific article; zbMATH DE number 3876594

Cites work

• A Graph Model for Fault-Tolerant Computing Systems
• Edge fault tolerance in graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 913340 (Why is no real title available?)

Cited in

(26)

• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• Extension complexity of stable set polytopes of bipartite graphs
• The matching extension problem in general graphs is co-NP-complete
• On the complexity of solution extension of optimization problems
• On the complexity of computing the excessive \([B]\)-index of a graph
• T-irreducible extension of polygonal digraphs
• scientific article; zbMATH DE number 5811090 (Why is no real title available?)
• scientific article; zbMATH DE number 3874608 (Why is no real title available?)
• scientific article; zbMATH DE number 89391 (Why is no real title available?)
• scientific article; zbMATH DE number 867710 (Why is no real title available?)
• Vertex extensions of 4-layer graphs and hypercubes
• Construction of all minimal edge extensions of the graph with isomorphism rejection
• scientific article; zbMATH DE number 7310088 (Why is no real title available?)
• Characterization of graphs with a given number of additional edges in a minimal 1-vertex extension
• scientific article; zbMATH DE number 7310216 (Why is no real title available?)
• scientific article; zbMATH DE number 7310226 (Why is no real title available?)
• UPPER BOUND FOR THE NUMBER OF ADDITIONAL EDGES IN MINIMAL 1-EDGE EXTENSIONS OF STARLIKE TREES
• T-irreducible extensions of directed starlike trees
• ON MINIMAL VERTEX 1-EXTENSIONS OF PATH ORIENTATION
• On the \({\mathcal {H}}\)-free extension complexity of the TSP
• Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives
• Algorithms for #BIS-hard problems on expander graphs
• About uniqueness of the minimal 1-edge extension of hypercube Q4
• Recognizing \(k\)-clique extendible orderings
• Recognizing \(k\)-clique extendible orderings
• An extension of a fixed point problem for simple graphs

This page was built for publication: On the complexity of some problems related to graph extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650325)