198,416 research outputs found
Primerjava vloge vojaških specialnih enot Slovenije in ZDA v sodobnih oboroženih spopadih
No full text
Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound
No full textPoljak 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 graph G 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 edges guaranteed by the Poljak-Turzík bound.
We consider properties Pi for which the Above Poljak-Turzík problem is fixed-parameter tractable (FPT) on graphs which are O(k) vertices away from being a graph in which each block is a clique. We show that for all such properties, Above Poljak-Turzík is FPT for all 0< lambda <1. Our results hold for properties of oriented graphs and graphs with edge labels.
Our results generalize the recent result of Crowston et al. (ICALP 2012) on MAXCUT parameterized above the Edwards-Erdos, and yield FPT algorithms for several graph problems parameterized above lower bounds. For instance, we get that the above-guarantee Max q-Colorable Subgraph problem is FPT. Our results also imply that the parameterized above-guarantee Oriented Max Acyclic Digraph problem thus solving an open question of Raman and Saurabh (Theor. Comput. Sci. 2006)
Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound
No full textPoljak 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 graph G 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 edges guaranteed by the Poljak-Turzík bound. We consider properties Pi for which the Above Poljak-Turzík problem is fixed-parameter tractable (FPT) on graphs which are O(k) vertices away from being a graph in which each block is a clique. We show that for all such properties, Above Poljak-Turzík is FPT for all 0< lambda <1. Our results hold for properties of oriented graphs and graphs with edge labels. Our results generalize the recent result of Crowston et al. (ICALP 2012) on MAXCUT parameterized above the Edwards-Erdos, and yield FPT algorithms for several graph problems parameterized above lower bounds. For instance, we get that the above-guarantee Max q-Colorable Subgraph problem is FPT. Our results also imply that the parameterized above-guarantee Oriented Max Acyclic Digraph problem thus solving an open question of Raman and Saurabh (Theor. Comput. Sci. 2006)
Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound
No full textPoljak and Turzik (Discrete Mathematics 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 graph G on n vertices and m edges contains a spanning subgraph H in Pi with at least lambda*m+(1-lambda)(n-1)/2 edges. The property of being bipartite is
lambda-extendible for lambda =1/2, and so the Poljak-Turzik bound
generalizes the well-known Edwards-Erdos bound for Max Cut. Other examples of lambda-extendible properties include: being an acyclic oriented graph, a balanced signed graph, or a q-colorable graph for some q in N.
Mnich et al. (FSTTCS 2012) defined the closely related notion of strong lambda-extendibility. They showed that the problem of finding a subgraph satisfying a given strongly lambda-extendible property Pi is fixed-parameter tractable (FPT) when parameterized above the Poljak-Turzik bound---does there exist a spanning subgraph H of a connected graph G such that H in Pi and H has at least lambda*m+(1-lambda)(n-1)/2+k edges?---subject to the condition that the problem is FPT on a certain simple class of graphs called almost-forests of cliques. This generalized an earlier result of Crowston et al. (ICALP 2012) for Max Cut, to all strongly lambda-extendible properties which satisfy the additional criterion.
In this paper we settle the kernelization complexity of nearly all problems parameterized above Poljak-Turzik bounds, in the affirmative. We show that these problems admit quadratic kernels (cubic when lambda=1/2), without using the assumption that the problem is FPT on almost-forests of cliques. Thus our results not only remove the technical condition of being FPT on almost-forests of cliques from previous results, but also unify and extend previously known kernelization results in this direction. Our results add to the select list of generic kernelization results known in the literature
Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
No full textMaxCut is a classical NP-complete problem and a crucial building block in many
combinatorial algorithms. The famousEdwards-Erdös bound states that any connected
graph on n vertices with m edges contains a cut of size at least m/2 + n−1/4 . Crowston,
Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple
connected graphs admits an FPT algorithm, where the parameter k is the difference
between the desired cut size c and the lower bound given by the Edwards-Erdös
bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run
in parameterized linear time, i.e., f (k) · O(m). We improve upon this result in two
ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively,
graphs with positive integer weights). Secondly, we change the parameter; instead of
the difference to the Edwards-Erdös bound, we use the difference to the Poljak-Turzík
bound. The Poljak-Turzík bound states that any weighted graph G has a cut of weight
at least w(G)/2 + wMSF (G)/4 , where w(G) denotes the total weight of G, and wMSF (G)
denotes the weight of its minimum spanning forest. In connected simple graphs the
two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger
and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear
time, i.e., f (k) · O(m + n)
Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
No full textMaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdős bound states that any connected graph on n vertices with m edges contains a cut of size at least . Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdős bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., . We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdős bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of size at least , where w(G) denotes the total weight of G, and denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., .20 page
Beyond {Max-Cut}: -extendible Properties Parameterized above the {Poljak--Turz\'{i}k} Bound
No full textWe 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(p) 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 h?p and h has at least ?m+1-?2(n-1)+k edges — is fixed-parameter tractable (fpt) for all
Socio-material security of active illicit drug users
No full textNaloga v teoretičnem delu oriše sistem socialne varnosti v Sloveniji, kjer predstaviva tudi denarne transferje. Nadaljujeva s politiko na področju drog in s tem povezano socialno varnostjo aktivnih uživalcev nedovoljenih drog. Opiševa tudi njim namenjene programe, njihovo socialno mrežo, vpletenost na trg dela in strategije za zagotavljanje preživetja. Zaključiva s predstavitvijo univerzalnega temeljnega dohodka.
V empiričnem delu predstaviva zgodbe in poglede šestih uživalcev nedovoljenih drog. V ugotovitvah povzameva njihova pričevanja in jih oblikujeva v sklepe, ki orišejo njihovo socialno-materialno situacijo, strategije preživetja ter njihov pogled na koncept univerzalnega temeljnega dohodka.
S pogovori z intervjuvanci sva spoznali življenjski svet uporabnika nedovoljenih drog. Dobili sva natančnejšo sliko o njihovih dohodkih, stroških, različnih strategijah povečevanja prihodkov in mnenja o konceptu univerzalnega temeljnega dohodka ter s tem oris njihovih potreb.In the theoretical part, we outline the social security system in Slovenia, where we also present cash transfers. We continue with the drug policy and the related social security of active illicit drug users. It also describes their programs, their social network, labor market involvement and survival strategies. We conclude with a presentation of the universal basic income.
In the empirical part, we present the stories and views of six illicit drug users. In the findings, we summarize their testimonies and shape them into conclusions that outline their socio-material situation, survival strategies and their view of the concept of universal basic income.
Through conversations we got to know the world of an illicit drug user. We got a more detailed picture of their income, expenses, different strategies for increasing their income and opinions on the concept of universal basic income, and an outline of their needs
- …
