A labeling algorithm to recognize a line digraph and output its root graph

DOI10.1016/0020-0190(82)90080-1zbMath0483.68062WikidataQ56388861 ScholiaQ56388861MaRDI QIDQ1163377

Maciej M. Sysło

Publication date: 1982

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(82)90080-1

zbMATH Keywords

recognition algorithm

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

Related Items

Parallel interval order recognition and construction of interval representations, Minimizing completion time for a class of scheduling problems, Optimal constructions of reversible digraphs, Minimizing the jump number for partially ordered sets: A graph-theoretic approach, An algorithm for minimizing setups in precedence constrained scheduling, On some complexity properties of N-free posets and posets with bounded decomposition diameter, On finding the jump number of a partial order by substitution decomposition, N-free posets as generalizations of series-parallel posets, Transitive closure for restricted classes of partial orders, \(N\)-free orders and minimal interval extensions, Parallel \(N\)-free order recognition, The forbidden minor characterization of line-search antimatroids of rooted digraphs, Review of properties of different precedence graphs for scheduling problems, Reconstructing a graph from its arc incidence graph, Characterization of classical graph classes by weighted clique graphs, On Page Number of N-free Posets

Cites Work

• Unnamed Item
• An algorithm to recognize a middle graph
• Optimal constructions of event-node networks
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Line pseudodigraphs