Beyond Max-Cut: ?-Extendible Properties Parameterized Above the Poljak-Turzík Bound

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F14%3A00221005" target="_blank" >RIV/68407700:21240/14:00221005 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.sciencedirect.com/science/article/pii/S0022000014000555" target="_blank" >http://www.sciencedirect.com/science/article/pii/S0022000014000555</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jcss.2014.04.011" target="_blank" >10.1016/j.jcss.2014.04.011</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Beyond Max-Cut: ?-Extendible Properties Parameterized Above the Poljak-Turzík Bound

Popis výsledku v původním jazyce

We define strong ?-extendibility as a variant of the notion of ?-extendible properties of graphs (Poljak and Turzík, Discrete Mathematics, 1986). We show that the parameterized APT(?) problem?given a connected graph G on n vertices and m edges and an integer parameter k, does there exist a spanning subgraph H of G such that Helement? and H has at least ?m+(1-?)/2*(n-1)+k edges?is fixed-parameter tractable (FPT) for all 0<?<1, for all strongly ?-extendible graph properties ? for which the APT(?) problemis FPT on graphs which are O(k) vertices away from being a graph in which each block is a clique. Our results hold for properties of oriented graphs and graphs with edge labels, generalize the recent result of Crowston et al. (ICALP 2012) on Max-Cut parameterized above the Edwards?Erdős bound, and yield FPT algorithms for several graph problems parameterized above lower bounds.

Název v anglickém jazyce

Beyond Max-Cut: ?-Extendible Properties Parameterized Above the Poljak-Turzík Bound

Popis výsledku anglicky

We define strong ?-extendibility as a variant of the notion of ?-extendible properties of graphs (Poljak and Turzík, Discrete Mathematics, 1986). We show that the parameterized APT(?) problem?given a connected graph G on n vertices and m edges and an integer parameter k, does there exist a spanning subgraph H of G such that Helement? and H has at least ?m+(1-?)/2*(n-1)+k edges?is fixed-parameter tractable (FPT) for all 0<?<1, for all strongly ?-extendible graph properties ? for which the APT(?) problemis FPT on graphs which are O(k) vertices away from being a graph in which each block is a clique. Our results hold for properties of oriented graphs and graphs with edge labels, generalize the recent result of Crowston et al. (ICALP 2012) on Max-Cut parameterized above the Edwards?Erdős bound, and yield FPT algorithms for several graph problems parameterized above lower bounds.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2014

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Computer and System Sciences

ISSN

0022-0000

e-ISSN

—

Svazek periodika

80

Číslo periodika v rámci svazku

7

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

20

Strana od-do

1384-1403

Kód UT WoS článku

000336882100014

EID výsledku v databázi Scopus

—