ALGORITHMS FOR SOLVING SYSTEMS OF EQUATIONS OVER VARIOUS CLASSES OF FINITE GRAPHS

DOI10.17223/20710410/53/6MaRDI QIDQ5155648zbMATH OpenOpenAlexFDO

Authors Artëm Viktorovich V. Il'ev, Victor Petrovich Il'ev

Publication date 8 October 2021

Published in Prikladnaya Diskretnaya Matematika (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/pdm748

zbMATH Keywords

computational complexitygraphsystem of equations

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX)

Recommendations

• On complexity of solving of equations over graphs
• The complexity of solving equations over finite groups
• Counting the solutions of a system of equations over finite field is NP-hard
• Graph colourings and solutions of systems of equations over finite fields
• Dichotomies in the complexity of solving systems of equations over finite semigroups

Cited in

(6)

• Systems of Diophantine equations over finite configurations
• A graph-theoretic algorithm for constructing a committee of an inconsistent system of linear inequalities
• On systems of equations defining infinite graphs
• On complexity of solving of equations over graphs
• The NP-completeness of the consistency problem for systems of Diophantine equations over finite configurations
• Axiomatizability and decidability of universal theories of hereditary classes of models of finite and infinite languages

This page was built for publication: ALGORITHMS FOR SOLVING SYSTEMS OF EQUATIONS OVER VARIOUS CLASSES OF FINITE GRAPHS

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