Shortest longest-path graph orientations

DOI10.1007/978-3-031-49190-0_10MaRDI QIDQ6591464

Hirotaka Ono, Eiji Miyano, Shay Zakov, Quan Xue, Avraham A. Melkman, Jesper Jansson, Yuichi Asahiro

Publication date: 22 August 2024

zbMATH Keywords

algorithmcomputational complexitygraph coloringpath graphstar graphgraph orientationcycle graph

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• The minimum broadcast time problem for several processor networks
• A linear-time algorithm for concave one-dimensional dynamic programming
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Planar orientations with low out-degree and compaction of adjacency matrices
• Acyclic orientations of a graph and the chromatic and independence numbers
• Minimizing maximum indegree
• On the range maximum-sum segment query problem
• On the Approximability of Reachability-Preserving Network Orientations
• Reducibility among Combinatorial Problems
• On-line dynamic programming with applications to the prediction of RNA secondary structure
• Egalitarian Graph Orientations
• Nombre chromatique et plus longs chemins d'un graphe
• Zur algebraischen Begründung der Graphentheorie. I
• Graph Orientations Optimizing the Number of Light or Heavy Vertices

This page was built for publication: Shortest longest-path graph orientations

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