A method of graph reduction and its applications

DOI10.1515/DMA-2018-0022MaRDI QIDQ1669583zbMATH OpenOpenAlexWikidataFDO

Authors Dmitrii V. Sirotkin, D. S. Malyshev

Publication date 3 September 2018

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/dma-2018-0022

zbMATH Keywords

computational complexityplanar graphindependent setsplanar triangulation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Publication:3032302
• Reduction graph and its application on algebraic graphs
• scientific article; zbMATH DE number 177426
• An algebraic theory of graph reduction
• scientific article; zbMATH DE number 1231509
• scientific article; zbMATH DE number 124283
• New methods for reducing size graphs
• A reduction of the graph reconstruction conjecture
• An algorithm for transitive reduction of an acyclic graph
• Reductions to graph isomorphism

Cites work

• scientific article; zbMATH DE number 6004934 (Why is no real title available?)
• scientific article; zbMATH DE number 3700235 (Why is no real title available?)
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• Efficient Planarity Testing
• Local transformations of graphs preserving independence number
• On the maximum independent set problem in subclasses of planar graphs
• On the maximum independent set problem in subclasses of subcubic graphs
• Some simplified NP-complete graph problems

Cited in

(14)

• An algorithm for transitive reduction of an acyclic graph
• The Maximum Independent Set Problem in Planar Graphs
• Independence and irredundance in \(k\)-regular graphs
• A new reduction rule for the connection graph proof procedure
• Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
• scientific article; zbMATH DE number 124283 (Why is no real title available?)
• On reducing maximum independent set to minimum satisfiability
• scientific article; zbMATH DE number 2208652 (Why is no real title available?)
• A constructive existence theorem related to local transformations of graphs for the independent set problem
• scientific article; zbMATH DE number 786176 (Why is no real title available?)
• On the reduction of Yutsis graphs
• A graph-transformational approach for proving the correctness of reductions between NP-problems
• On the hardness of computing maximum self-reduction sequences
• scientific article; zbMATH DE number 177426 (Why is no real title available?)

This page was built for publication: A method of graph reduction and its applications

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