Approximating Shortest Connected Graph Transformation for Trees

DOI10.1007/978-3-030-38919-2_7zbMath1440.68183OpenAlexW2999396581MaRDI QIDQ3297756

Alice Joffard, Nicolas Bousquet

Publication date: 20 July 2020

Published in: SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-38919-2_7

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (2)

On the longest flip sequence to untangle segments in the plane ⋮ Complexity results on untangling red-blue matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconfiguration of graphs with connectivity constraints
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Introduction to reconfiguration
• Graph Theory
• Transforming cabbage into turnip
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Switching Distance Between Graphs with the Same Degrees
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph II. Uniqueness
• Partitions and Their Representative Graphs

This page was built for publication: Approximating Shortest Connected Graph Transformation for Trees