An \(O(n\log n)\) algorithm for finding edge span of cacti

DOI10.1007/s10878-015-9827-4zbMath1339.05137DBLPjournals/jco/JanczewskiT16OpenAlexW2101461335WikidataQ59472539 ScholiaQ59472539MaRDI QIDQ281767

Krzysztof Turowski, Robert Janczewski

Publication date: 11 May 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-015-9827-4

zbMATH Keywords

vertex coloringedge spancacti

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Edge coloring of graphs of signed class 1 and 2

Cites Work

• Unnamed Item
• The complexity of the \(L(p,q)\)-labeling problem for bipartite planar graphs of small degree
• \(T\)-colorings and \(T\)-edge spans of graphs
• A survey on labeling graphs with a condition at distance two
• Labelling Graphs with a Condition at Distance 2
• Reducibility among Combinatorial Problems
• Combinatorial Geometry and Graph Theory
• The edge span of distance two labellings of graphs

This page was built for publication: An \(O(n\log n)\) algorithm for finding edge span of cacti