TY - GEN
T1 - On the recognition of k-equistable graphs
AU - Levit, Vadim E.
AU - Milanič, Martin
AU - Tankus, David
N1 - Funding Information:
MM is supported in part by “Agencija za raziskovalno dejavnost Republike Slovenije”, research program P1–0285 and research projects J1–4010, J1–4021 and N1–0011. Research was partly done during a visit of the second author at the Department of Computer Science and Mathematics at the Ariel University Center of Samaria in the frame of a Slovenian Research Agency project MU-PROM/11-007. The second author thanks the Department for its hospitality and support.
PY - 2012
Y1 - 2012
N2 - A graph G∈=∈(V,E) is called equistable if there exist a positive integer t and a weight function such that S∈⊆∈V is a maximal stable set of G if and only if w(S)∈=∈t. The function w, if exists, is called an equistable function of G. No combinatorial characterization of equistable graphs is known, and the complexity status of recognizing equistable graphs is open. It is not even known whether recognizing equistable graphs is in NP. Let k be a positive integer. An equistable graph G∈=∈(V,E) is said to be k-equistable if it admits an equistable function which is bounded by k. For every constant k, we present a polynomial time algorithm which decides whether an input graph is k-equistable.
AB - A graph G∈=∈(V,E) is called equistable if there exist a positive integer t and a weight function such that S∈⊆∈V is a maximal stable set of G if and only if w(S)∈=∈t. The function w, if exists, is called an equistable function of G. No combinatorial characterization of equistable graphs is known, and the complexity status of recognizing equistable graphs is open. It is not even known whether recognizing equistable graphs is in NP. Let k be a positive integer. An equistable graph G∈=∈(V,E) is said to be k-equistable if it admits an equistable function which is bounded by k. For every constant k, we present a polynomial time algorithm which decides whether an input graph is k-equistable.
KW - equistable graph
KW - maximal stable set
KW - polynomial time algorithm
UR - https://www.scopus.com/pages/publications/84868007712
U2 - 10.1007/978-3-642-34611-8_29
DO - 10.1007/978-3-642-34611-8_29
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:84868007712
SN - 9783642346101
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 286
EP - 296
BT - Graph-Theoretic Concepts in Computer Science - 38th International Workshop, WG 2012, Revised Selcted Papers
T2 - 38th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2012
Y2 - 26 June 2012 through 28 June 2012
ER -