A method of graph reduction and its applications
DOI10.1515/DMA-2018-0022zbMATH Open1394.05094OpenAlexW2888414688WikidataQ129354095 ScholiaQ129354095MaRDI QIDQ1669583FDOQ1669583
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
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
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)
Cites Work
- Efficient Planarity Testing
- Some simplified NP-complete graph problems
- Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
- On the maximum independent set problem in subclasses of subcubic graphs
- On the maximum independent set problem in subclasses of planar graphs
- Local transformations of graphs preserving independence number
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (14)
- The Maximum Independent Set Problem in Planar Graphs
- An algorithm for transitive reduction of an acyclic graph
- Independence and irredundance in \(k\)-regular graphs
- Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
- A new reduction rule for the connection graph proof procedure
- Title not available (Why is that?)
- On reducing maximum independent set to minimum satisfiability
- Title not available (Why is that?)
- A constructive existence theorem related to local transformations of graphs for the independent set problem
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
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)
