Buchumschlag

Forcing a unique minimum spanning tree and a unique shortest path

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Gima, Tatsuya, Kobayashi, Yasuaki, Otachi, Yota, Sato, Takumi
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Hitting Geodesic Intervals in Structurally Restricted Graphs
von: Gima, Tatsuya, et al.
Veröffentlicht: (2025)

Computing diverse pair of solutions for tractable SAT
von: Gima, Tatsuya, et al.
Veröffentlicht: (2024)

Structural Parameterizations of Vertex Integrity
von: Gima, Tatsuya, et al.
Veröffentlicht: (2023)

Treewidth of the $n \times n$ toroidal grid
von: Gima, Tatsuya, et al.
Veröffentlicht: (2026)

Spanning tree congestion of proper interval graphs
von: Otachi, Yota
Veröffentlicht: (2026)

Dichotomies for Tree Minor Containment with Structural Parameters
von: Gima, Tatsuya, et al.
Veröffentlicht: (2023)

Structural Parameterizations of $k$-Planarity
von: Gima, Tatsuya, et al.
Veröffentlicht: (2025)

An improved spectral lower bound of treewidth
von: Gima, Tatsuya, et al.
Veröffentlicht: (2024)

Broadcasting under Structural Restrictions
von: Egami, Yudai, et al.
Veröffentlicht: (2025)

Biclique Reconfiguration in Bipartite Graphs
von: Otachi, Yota, et al.
Veröffentlicht: (2026)

Finding Order-Preserving Subgraphs
von: Imamura, Haruya, et al.
Veröffentlicht: (2025)

Finding Induced Subgraphs from Graphs with Small Mim-Width
von: Otachi, Yota, et al.
Veröffentlicht: (2024)

Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited
von: Hanaka, Tesshu, et al.
Veröffentlicht: (2025)

Sequentially Swapping Tokens: Further on Graph Classes
von: Kiya, Hironori, et al.
Veröffentlicht: (2022)

Courcelle's Theorem for Lipschitz Continuity
von: Gima, Tatsuya, et al.
Veröffentlicht: (2025)

On the complexity of finding a spanning even tree in a graph
von: Hanaka, Tesshu, et al.
Veröffentlicht: (2024)

Approximating the shortest path problem with scenarios
von: Kasperski, Adam, et al.
Veröffentlicht: (2018)

Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2024)

Interdiction of minimum spanning trees and other matroid bases
von: Weninger, Noah, et al.
Veröffentlicht: (2024)

Faster negative length shortest paths by bootstrapping hop reducers
von: Huang, Yufan, et al.
Veröffentlicht: (2025)

Are there graphs whose shortest path structure requires large edge weights?
von: Bernstein, Aaron, et al.
Veröffentlicht: (2023)

Recoverable robust shortest path problem under interval budgeted uncertainty representations
von: Jackiewicz, Marcel, et al.
Veröffentlicht: (2024)

Binary weights spanning trees and the $k$-red spanning tree problem in linear time
von: Hochbaum, Dorit S.
Veröffentlicht: (2024)

Solving the all pairs shortest path problem after minor update of a large dense graph
von: Liu, Gangli
Veröffentlicht: (2024)

Fast and Practical Single-Exponential Algorithms for Branchwidth
von: Kaneda, Taiki, et al.
Veröffentlicht: (2026)

Parameterized Complexity of Finding Dissimilar Shortest Paths
von: Funayama, Ryo, et al.
Veröffentlicht: (2024)

Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2020)

Faster single-source shortest paths with negative real weights via proper hop distance
von: Huang, Yufan, et al.
Veröffentlicht: (2024)

Subquadratic Submodular Maximization with a General Matroid Constraint
von: Kobayashi, Yusuke, et al.
Veröffentlicht: (2024)

The problem of computing a $2$-T-connected spanning subgraph with minimum number of edges in directed graphs
von: Jaberi, Raed, et al.
Veröffentlicht: (2024)

Graph neural networks extrapolate out-of-distribution for shortest paths
von: Nerem, Robert R., et al.
Veröffentlicht: (2025)

2-Layer Fan-Planarity in Polynomial Time
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2025)

Faster shortest-path algorithms using the acyclic-connected tree
von: Stefansson, Elis, et al.
Veröffentlicht: (2025)

Computational complexity of the recoverable robust shortest path problem in acyclic digraphs
von: Kasperski, Adam, et al.
Veröffentlicht: (2024)

Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2023)

Finding a Minimum Spanning Tree with a Small Non-Terminal Set
von: Hanaka, Tesshu, et al.
Veröffentlicht: (2023)

Centrality of shortest paths: Algorithms and complexity results
von: Phosavanh, Johnson, et al.
Veröffentlicht: (2024)

Bandwidth Parameterized by Cluster Vertex Deletion Number
von: Gima, Tatsuya, et al.
Veröffentlicht: (2023)

On graphs coverable by k shortest paths
von: Dumas, Maël, et al.
Veröffentlicht: (2022)

Computing largest minimum color-spanning intervals of imprecise points
von: Acharyya, Ankush, et al.
Veröffentlicht: (2024)