Color-avoiding connected spanning subgraphs with minimum number of edges

DOI10.1016/j.dam.2024.01.044arXiv2302.11035OpenAlexW4391720153MaRDI QIDQ6130205

József Pintér, Kitti Varga

Publication date: 2 April 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2302.11035

zbMATH Keywords

complexityspanning subgraphsmatroidsapproximation algorithmscolor-avoiding connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Enumeration in graph theory (05C30) Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• Independence and port oracles for matroids, with an application to computational learning theory
• On the complexity of color-avoiding site and bond percolation
• Approximating the smallest k -edge connected spanning subgraph by LP-rounding
• The computational complexity of matroid properties
• Algorithmic versus axiomatic definitions of matroids
• Biconnectivity approximations and graph carvings
• Networks
• A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem
• Color-avoiding percolation of random graphs: between the subcritical and the intermediate regime

This page was built for publication: Color-avoiding connected spanning subgraphs with minimum number of edges