Imagen de Portada

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Çivril, Ali
Formato:	Preprint
Publicado:	2023
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
por: Çivril, Ali
Publicado: (2024)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
por: Norose, Ryoma, et al.
Publicado: (2024)

3/2-Approximation for the Forest Augmentation Problem
por: Çivril, Ali
Publicado: (2024)

4/3-Approximation of Graphic TSP
por: Çivril, Ali
Publicado: (2023)

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
por: Kobayashi, Yusuke, et al.
Publicado: (2026)

Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity
por: Long, Yaowei, et al.
Publicado: (2024)

Approximate Spanning Tree Counting from Uncorrelated Edge Sets
por: Liu, Yang P., et al.
Publicado: (2025)

New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
por: Ameli, Afrouz Jabal, et al.
Publicado: (2026)

Budget and Profit Approximations for Spanning Tree Interdiction
por: Ostrovsky, Rafail, et al.
Publicado: (2025)

Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
por: Biedl, Therese, et al.
Publicado: (2024)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
por: Long, Yaowei, et al.
Publicado: (2024)

The Vertex-Attribute-Constrained Densest $k$-Subgraph Problem
por: Lu, Qiheng, et al.
Publicado: (2025)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
por: Black, Hadley, et al.
Publicado: (2025)

Finding Order-Preserving Subgraphs
por: Imamura, Haruya, et al.
Publicado: (2025)

Forbidden Subgraph Problems with Predictions
por: Böckenhauer, Hans-Joachim, et al.
Publicado: (2025)

Destroying Densest Subgraphs is Hard
por: Bazgan, Cristina, et al.
Publicado: (2024)

A Note on Approximability of Densest At-Least-k-Subgraph
por: Laekhanukit, Bundit, et al.
Publicado: (2026)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
por: Georgiadis, Loukas, et al.
Publicado: (2026)

In-depth Analysis of Densest Subgraph Discovery in a Unified Framework
por: Zhou, Yingli, et al.
Publicado: (2024)

Finding Small Complete Subgraphs Efficiently
por: Chen, Ke, et al.
Publicado: (2023)

Counting Cohesive Subgraphs with Hereditary Properties
por: Li, Rong-Hua, et al.
Publicado: (2024)

Subexponential Parameterized Algorithms for Hitting Subgraphs
por: Lokshtanov, Daniel, et al.
Publicado: (2024)

Packing Compact Subgraphs with Applications to Districting
por: Chen, Ho-Lin, et al.
Publicado: (2026)

A Better-Than-$5/4$-Approximation for Two-Edge Connectivity
por: Hommelsheim, Felix, et al.
Publicado: (2025)

A $\frac{4}{3}$-Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs
por: Neuwohner, Meike
Publicado: (2024)

A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
por: Zhou, Yi, et al.
Publicado: (2025)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
por: Dey, Palash, et al.
Publicado: (2026)

Space Complexity of Vertex Connectivity Oracles
por: Pettie, Seth, et al.
Publicado: (2022)

The Connected k-Vertex One-Center Problem on Graphs
por: Zhang, Jingru
Publicado: (2024)

The Complexity Landscape of Dynamic Distributed Subgraph Finding
por: Chang, Yi-Jun, et al.
Publicado: (2024)

Scalable $k$-clique Densest Subgraph Search
por: Ye, Xiaowei, et al.
Publicado: (2024)

Approximation of Spanning Tree Congestion using Hereditary Bisection
por: Kolman, Petr
Publicado: (2024)

Compact Conformal Subgraphs
por: Gollapudi, Sreenivas, et al.
Publicado: (2026)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
por: Bhattacharya, Sayan, et al.
Publicado: (2026)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
por: Fischer, Olivier, et al.
Publicado: (2025)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
por: Jiang, Yonggang, et al.
Publicado: (2025)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
por: Bhanja, Koustav, et al.
Publicado: (2025)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
por: Li, Xizhe, et al.
Publicado: (2026)

Almost Tight Bounds for Differentially Private Densest Subgraph
por: Dinitz, Michael, et al.
Publicado: (2023)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
por: Mitrović, Slobodan, et al.
Publicado: (2025)