20.500.12556/DKUM-95222 Efficient direct reconstruction of bipartite (multi)graphs from their line graphs through a characterization of their edges We study the line graphs of bipartite multigraphs, which naturally arise in combinatorics, game theory, and applications such as scheduling and motion planning. We introduce a new characterization of these graphs via valid partial assignments of the edges of the underlying bipartite multigraph to the vertices of its line graph. We show that an empty assignment extends to a complete one precisely when the graph is a line graph of a bipartite multigraph. Based on this, we design an O(∆(G)|E(G)|) algorithm that incrementally constructs such assignments. The algorithm also provides a data structure supporting efficient solutions to problems of maximum clique, maximum weighted clique, minimum clique cover, chromatic number, and independence number. For line graphs of bipartite simple graphs these problems become solvable in linear time, improving on previously known polynomial-time results. For general bipartite multigraphs, our method enhances the O(|V(G)| 3 ) recognition algorithm of Peterson and builds on the results of Demaine et al., Hedetniemi, Cook et al., and Gurvich and Temkin. UNO-graph line graph bipartite graph bipartite multigraph graph algorithm UNO-graf graf povezav dvodelni graf dvodelni multigraf grafovski algoritem true true true Angleški jezik Slovenski jezik Znanstveno delo 2025-09-09 12:18:31 2025-09-09 12:18:31 2025-09-10 03:37:02 0000-00-00 00:00:00 2025 0 0 17 str. iss. 17, [article no.] 2876 Vol. 13 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2025-07-17 2025-09-03 2025-09-05 37.018.43:004:616-036.21 248174339 10.3390/math13172876 2227-7390 https://www.mdpi.com/2227-7390/13/17/2876 1 565446c5-8d66-11f0-9299-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=197994 mathematics-13-02876-v2_(1).pdf mathematics-13-02876-v2_(1).pdf 1 4BC37062C9C753C32A5AF1F4835D85C0 9f5f7bd60df02ee159b26c4a59305a0fc8887f14809193f9cadbced88a8cd341 03148a4c-8d67-11f0-9299-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=197995 Fakulteta za organizacijske vede 0 0 0