Shortest longest-path graph orientations

DOI10.1007/978-3-031-49190-0_10MaRDI QIDQ6591464zbMATH OpenFDO

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

Publication date 22 August 2024

Full work available at URL https://doi.org/10.1007/978-3-031-49190-0_10

zbMATH Keywords

computational complexityalgorithmgraph coloringgraph orientationpath graphstar graphcycle graph

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• A linear-time algorithm for concave one-dimensional dynamic programming
• Acyclic orientations of a graph and the chromatic and independence numbers
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Egalitarian graph orientations
• Graph orientations optimizing the number of light or heavy vertices
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Minimizing maximum indegree
• Nombre chromatique et plus longs chemins d'un graphe
• On the approximability of reachability-preserving network orientations
• On the range maximum-sum segment query problem
• On-line dynamic programming with applications to the prediction of RNA secondary structure
• Planar orientations with low out-degree and compaction of adjacency matrices
• Reducibility among combinatorial problems
• The minimum broadcast time problem for several processor networks
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Zur algebraischen Begründung der Graphentheorie. I

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)