scientific article; zbMATH DE number 2080985

MaRDI QIDQ4474082zbMATH OpenFDO

Authors Hiroshi Nagamochi, Toshimasa Ishii

Publication date 4 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2223/22230124.htm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• On the minimum local-vertex-connectivity augmentation in graphs
• Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs
• A <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>4</mml:mn><mml:mo stretchy="false">/</mml:mo><mml:mn>3</mml:mn></mml:math>-approximation for the minimum 2-local-vertex-connectivity augmentation in a co
• Mathematical Foundations of Computer Science 2003
• On the optimal vertex-connectivity augmentation
• \(k\)-vertex-connectivity minimum augmentation for undirected unweighted graphs.
• Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs
• Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs
• A note on the vertex-connectivity augmentation problem
• Local edge-connectivity augmentation in hypergraphs is NP-complete

Cited in

(4)

• A <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>4</mml:mn><mml:mo stretchy="false">/</mml:mo><mml:mn>3</mml:mn></mml:math>-approximation for the minimum 2-local-vertex-connectivity augmentation in a connected graph
• Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
• Hardness of \(k\)-vertex-connected subgraph augmentation problem
• On the minimum local-vertex-connectivity augmentation in graphs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4474082)