The complexity of probabilistic lobbying

Autor: Jörg Rothe, Nicholas Mattei, Gábor Erdélyi, Judy Goldsmith, Henning Fernau, Daniel Binkele-Raible

Publikováno v: Discrete Optimization. 11:1-21

We propose models for lobbying in a probabilistic environment, in which an actor (called ''The Lobby'') seeks to influence voters' preferences of voting for or against multiple issues when the voters' preferences are represented in terms of probabili

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::4ae6100bd63905aa347cc1f8b8976da1
https://doi.org/10.1016/j.disopt.2013.10.003

Exact and Parameterized Algorithms for Max Internal Spanning Tree

Autor: Henning Fernau, Daniel Binkele-Raible, Mathieu Liedloff, Serge Gaspers

Publikováno v: Algorithmica
Algorithmica, Springer Verlag, 2013, 65 (1), pp.95-128. ⟨10.1007/s00453-011-9575-5⟩

We consider the $\mathcal{NP}$-hard problem of finding a spanning tree with a maximum number of internal vertices. This problem is a generalization of the famous Hamiltonian Path problem. Our dynamic-programming algorithms for general and degree-boun

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::06d27227ab412099f92189c26be1040d
https://doi.org/10.1007/s00453-011-9575-5

Breaking the 2n-barrier for Irredundance: Two lines of attack

Autor: Henning Fernau, Mathieu Liedloff, Ljiljana Brankovic, Alexander Langer, Dieter Kratsch, Daniel Binkele-Raible, Jakub Onufry Wojtaszczyk, Marek Cygan, Peter Rossmanith, Marcin Pilipczuk, Joachim Kneis

Publikováno v: Journal of Discrete Algorithms
Journal of Discrete Algorithms, Elsevier, 2011, 9 (3), pp.214-230

International audience; The lower and the upper irredundance numbers of a graph G, denoted ir(G) and IR(G), respectively, are conceptually linked to the domination and independence numbers and have numerous relations to other graph parameters. It has

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::402adf709512599d419cc724ea321371
https://doi.org/10.1016/j.jda.2011.03.002

A new upper bound for Max-2-SAT: A graph-theoretic approach

Autor: Daniel Binkele-Raible, Henning Fernau

Publikováno v: Journal of Discrete Algorithms. 8:388-401

In {\sc MaxSat}, we ask for an assignment which satisfies the maximum number of clauses for a boolean formula in CNF. We present an algorithm yielding a run time upper bound of $O^*(2^{\frac{1}{6.2158}})$ for {\sc Max-2-Sat} (each clause contains at

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::73e7ce9abb9fae2188f416b3685893b6
https://doi.org/10.1016/j.jda.2010.06.001

A Parameterized Route to Exact Puzzles: Breaking the $2^n$-barrier for irredundancy

Autor: Ljiljana Brankovic, Mathieu Liedloff, Dieter Kratsch, Alexander Langer, Peter Rossmanith, Henning Fernau, Daniel Binkele-Raible, Joachim Kneis

Publikováno v: Lecture Notes in Computer Science
CIAC'2010 : 7th International Conference on Algorithms and Complexity
CIAC'2010 : 7th International Conference on Algorithms and Complexity, May 2010, Rome, Italy. pp.311-322, ⟨10.1007/978-3-642-13073-1_28⟩
Lecture Notes in Computer Science ISBN: 9783642130724
CIAC

The lower and the upper irredundance numbers of a graph G, denoted ir(G) and IR(G) respectively, are conceptually linked to domination and independence numbers and have numerous relations to other graph parameters. It is a long-standing open question

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6092c760d754e53727550e7697378176
https://hal.archives-ouvertes.fr/hal-00461068