Standard

Automated proofs of upper bounds on the running time of splitting algorithms. / Fedin, Sergey S.; Kulikov, Alexander S.

в: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том 3162, 01.12.2004, стр. 248-259.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Fedin, SS & Kulikov, AS 2004, 'Automated proofs of upper bounds on the running time of splitting algorithms', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 3162, стр. 248-259.

APA

Fedin, S. S., & Kulikov, A. S. (2004). Automated proofs of upper bounds on the running time of splitting algorithms. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3162, 248-259.

Vancouver

Fedin SS, Kulikov AS. Automated proofs of upper bounds on the running time of splitting algorithms. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2004 Дек. 1;3162:248-259.

Author

Fedin, Sergey S. ; Kulikov, Alexander S. / Automated proofs of upper bounds on the running time of splitting algorithms. в: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2004 ; Том 3162. стр. 248-259.

BibTeX

@article{f59cabcd2ee245eeb7f0e651591154f0,
title = "Automated proofs of upper bounds on the running time of splitting algorithms",
abstract = "The splitting method is one of the most powerful and wellstudied approaches for solving various NP-hard problems. The main idea of this method is to split an input instance of a problem into several simpler instances (further simplified by certain simplification rules), such that when the solution for each of them is found, one can construct the solution for the initial instance in polynomial time. There exists a huge number of articles describing algorithms of this type and usually a considerable part of such an article is devoted to case analysis. In this paper we show how it is possible to write a program that given simplification rules would automatically generate a proof of an upper bound on the running time of a splitting algorithm that uses these rules. As an example we report the results of experiments with such a program for the SAT, MAXSAT, and (n,3)-MAXSAT (the MAXSAT problem for the case where every variable in the formula appears at most three times) problems.",
author = "Fedin, {Sergey S.} and Kulikov, {Alexander S.}",
year = "2004",
month = dec,
day = "1",
language = "English",
volume = "3162",
pages = "248--259",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer Nature",

}

RIS

TY - JOUR

T1 - Automated proofs of upper bounds on the running time of splitting algorithms

AU - Fedin, Sergey S.

AU - Kulikov, Alexander S.

PY - 2004/12/1

Y1 - 2004/12/1

N2 - The splitting method is one of the most powerful and wellstudied approaches for solving various NP-hard problems. The main idea of this method is to split an input instance of a problem into several simpler instances (further simplified by certain simplification rules), such that when the solution for each of them is found, one can construct the solution for the initial instance in polynomial time. There exists a huge number of articles describing algorithms of this type and usually a considerable part of such an article is devoted to case analysis. In this paper we show how it is possible to write a program that given simplification rules would automatically generate a proof of an upper bound on the running time of a splitting algorithm that uses these rules. As an example we report the results of experiments with such a program for the SAT, MAXSAT, and (n,3)-MAXSAT (the MAXSAT problem for the case where every variable in the formula appears at most three times) problems.

AB - The splitting method is one of the most powerful and wellstudied approaches for solving various NP-hard problems. The main idea of this method is to split an input instance of a problem into several simpler instances (further simplified by certain simplification rules), such that when the solution for each of them is found, one can construct the solution for the initial instance in polynomial time. There exists a huge number of articles describing algorithms of this type and usually a considerable part of such an article is devoted to case analysis. In this paper we show how it is possible to write a program that given simplification rules would automatically generate a proof of an upper bound on the running time of a splitting algorithm that uses these rules. As an example we report the results of experiments with such a program for the SAT, MAXSAT, and (n,3)-MAXSAT (the MAXSAT problem for the case where every variable in the formula appears at most three times) problems.

UR - http://www.scopus.com/inward/record.url?scp=35048897430&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:35048897430

VL - 3162

SP - 248

EP - 259

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -

ID: 49824623