On the complexity of some problems related to graph extensions
DOI10.1134/S0001434610110015zbMATH Open1232.05056OpenAlexW2044737433MaRDI QIDQ650325FDOQ650325
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
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
fault tolerance\(NP\) problem\(NP\)-complete problemexact \(k\)-extensionextension of graphsirreducible \(k\)-extensionminimal \(k\)-extensionvertex and edge \(k\)-extension
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex degrees (05C07)
Cites Work
Cited In (23)
- An extension of a fixed point problem for simple graphs
- Title not available (Why is that?)
- T-irreducible extensions of directed starlike trees
- Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives
- Construction of all minimal edge extensions of the graph with isomorphism rejection
- Vertex extensions of 4-layer graphs and hypercubes
- About uniqueness of the minimal 1-edge extension of hypercube Q4
- T-irreducible extension of polygonal digraphs
- The matching extension problem in general graphs is co-NP-complete
- Title not available (Why is that?)
- Algorithms for #BIS-hard problems on expander graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- UPPER BOUND FOR THE NUMBER OF ADDITIONAL EDGES IN MINIMAL 1-EDGE EXTENSIONS OF STARLIKE TREES
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- On the complexity of computing the excessive \([B]\)-index of a graph
- Recognizing \(k\)-clique extendible orderings
- Title not available (Why is that?)
- Extension complexity of stable set polytopes of bipartite graphs
- ON MINIMAL VERTEX 1-EXTENSIONS OF PATH ORIENTATION
- Title not available (Why is that?)
- Characterization of graphs with a given number of additional edges in a minimal 1-vertex extension
- On the \({\mathcal {H}}\)-free extension complexity of the TSP
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)
