Lexicographic orientation algorithms

DOI10.1007/978-3-319-71840-8_12MaRDI QIDQ3120444zbMATH OpenOpenAlexFDO

Authors Jing Huang

Publication date 4 March 2019

Published in Springer Monographs in Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-71840-8_12

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Recommendations

• Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees
• Oriented graph coloring
• On the orientation of graphs and hypergraphs
• Approximation algorithms for orienting mixed graphs
• scientific article; zbMATH DE number 17787

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• A translation of Gallai's paper: `Transitiv orientierbare Graphen'
• Algorithmic Aspects of Vertex Elimination on Graphs
• An Efficient Test for Circular-Arc Graphs
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Characterizing circular-arc graphs
• Circular-arc graphs with clique cover number two
• Coloring a Family of Circular Arcs
• Completing orientations of partially oriented graphs
• Disjoint paths in tournaments
• Graph Sandwich Problems
• Highly connected non-2-linked digraphs
• scientific article; zbMATH DE number 3172312 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1334633 (Why is no real title available?)
• scientific article; zbMATH DE number 3205929 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
• Linear-time recognition of circular-arc graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• List homomorphisms and circular arc graphs
• Locally semicomplete digraphs: A generalization of tournaments
• Matrix characterizations of circular-arc graphs
• Modular decomposition and transitive orientation
• Nombre chromatique et plus longs chemins d'un graphe
• On Frank's conjecture on \(k\)-connected orientations
• On the structure of local tournaments
• Quasi‐transitive digraphs
• Representation characterizations of chordal bipartite graphs
• Representation of a finite graph by a set of intervals on the real line
• Restricted cycle factors and arc-decompositions of digraphs
• Robbins's Theorem for Mixed Multigraphs
• Strongly 2-connected orientations of graphs
• The complexity of comparability graph recognition and coloring
• The directed subgraph homeomorphism problem
• Transitiv orientierbare Graphen
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Two remarks on circular arc graphs

Cited in

(1)

• Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees

This page was built for publication: Lexicographic orientation algorithms

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