Improved Approximations for Extremal Eigenvalues of Sparse Hamiltonians

Autor: Hothem, Daniel, Parekh, Ojas, Thompson, Kevin

We give a classical $1/(qk+1)$-approximation for the maximum eigenvalue of a $k$-sparse fermionic Hamiltonian with strictly $q$-local terms, as well as a $1/(4k+1)$-approximation when the Hamiltonian has both $2$-local and $4$-local terms. More gener

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

Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument

Autor: Majewski, Konrad, Masařík, Tomáš, Novotná, Jana, Okrasa, Karolina, Pilipczuk, Marcin, Rzążewski, Paweł, Sokołowski, Marek

Publikováno v: 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022

We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw S_{t,t,t} as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomassé, SODA 2020] and provide a subexponential-time algorithm

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

Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults

Autor: Adjiashvili, David, Hommelsheim, Felix, Mühlenthaler, Moritz, Schaudt, Oliver

Publikováno v: Leibniz International Proceedings in Informatics (LIPIcs), 227

The Edge-disjoint s-t Paths Problem (s-t EDP) is a classical network design problem whose goal is to connect for some k ≥ 1 two given vertices of a graph under the condition that any k - 1 edges of the graph may fail. We extend the simple uniform f

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3537561a0c7e9717067933f94e555aa8
https://hdl.handle.net/20.500.11850/557702

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

Online Spanners in Metric Spaces

Autor: Bhore, Sujoy, Filtser, Arnold, Khodabandeh, Hadi, Tóth, Csaba D.

Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric t-spanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite set

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