Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F12%3A00203711" target="_blank" >RIV/68407700:21240/12:00203711 - isvavai.cz</a>
Result on the web
<a href="http://drops.dagstuhl.de/opus/volltexte/2012/3877/" target="_blank" >http://drops.dagstuhl.de/opus/volltexte/2012/3877/</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.412" target="_blank" >10.4230/LIPIcs.FSTTCS.2012.412</a>
Alternative languages
Result language
angličtina
Original language name
Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound
Original language description
Poljak and Turzík (Discrete Math. 1986) introduced the notion of lambda-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0 < lambda < 1 and lambda-extendible property Pi, any connected graphG on n vertices and m edges contains a spanning subgraph H in Pi with at least lambda m+ (1-lambda)/2 (n-1) edges. The property of being bipartite is lambda-extendible for lambda=1/2, and thus the Poljak-Turzík bound generalizes the well-known Edwards-Erdos bound for MAXCUT. We define a variant, namely strong lambda-extendibility, to which the Poljak-Turzík bound applies. For a strong lambda-extendible graph property Pi, we define the parameterized Above Poljak-Turzík problem as follows: 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 H in Pi and H has at least lambda m+ (1-lambda)/2 (n-1)+k edges? The parameter is k, the surplus over the number of ed
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
ISBN
978-3-939897-47-7
ISSN
1868-8969
e-ISSN
—
Number of pages
12
Pages from-to
412-423
Publisher name
Schloss Dagstuhl - Leibniz Center for Informatics
Place of publication
Wadern
Event location
Hyderabad
Event date
Dec 15, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—