Complexity of Finding Maximum Locally Irregular Induced Subgraphs

Autor: Fioravantes, Foivos, Melissinos, Nikolaos, Triommatis, Theofilos

Publikováno v: [Research Report] Inria; I3S; Université Côte d'Azur. 2021
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2022
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2022, Jun 2022, Torshavn, Faroe Islands. ⟨10.4230/LIPIcs.SWAT.2022.23⟩

If a graph G is such that no two adjacent vertices of G have the same degree, we say that G is locally irregular. In this work we introduce and study the problem of identifying a largest induced subgraph of a given graph G that is locally irregular.

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8aad280c8db6a41199f6ce60306b74a1

A Parameterized Perspective on Attacking and Defending Elections

Autor: Gowda, Kishen N., Misra, Neeldhara, Patel, Vraj

Publikováno v: Combinatorial Algorithms

We consider the problem of protecting and manipulating elections by recounting and changing ballots, respectively. Our setting involves a plurality-based election held across multiple districts, and the problem formulations are based on the model pro

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=pmc_________::bfd21808f7031a8397c9df4c4f3d3823
http://europepmc.org/articles/PMC7254901

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Parameterized Pre-coloring Extension and List Coloring Problems

Autor: Gregory Gutin, Magnus Wahlström, Sebastian Ordyniak, Diptapriyo Majumdar

Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the parameterized complexity of the following problems parameterized by k: (1) Given a graph G, a clique modulator D (a clique modulator is a set of vertices, whose removal results in

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f158e8ac9f8ca03297e7782c2b1419c3
http://arxiv.org/abs/1907.12061

Finding large degree-anonymous subgraphs is hard

Autor: Cristina Bazgan, Robert Bredereck, Sepp Hartung, Gerhard J. Woeginger, André Nichterlein

Publikováno v: Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2016, 622, ⟨10.1016/j.tcs.2016.02.004⟩
Theoretical Computer Science, 622, 90-110. Elsevier

International audience; A graph is said to be k-anonymous for an integer k, if for every vertex in the graph there are at least k−1k−1 other vertices with the same degree. We examine the computational complexity of making a given undirected graph

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::21c274bcfb8adf93c60f3edb9e8fb578
https://doi.org/10.1016/j.tcs.2016.02.004