| Naslov: | Efficient direct reconstruction of bipartite (multi)graphs from their line graphs through a characterization of their edges |
|---|
| Avtorji: | ID Bokal, Drago (Avtor)
ID Jerebic, Janja (Avtor) |
|---|
| Datoteke: |  https://www.mdpi.com/2227-7390/13/17/2876
 mathematics-13-02876-v2_(1).pdf (348,95 KB)
MD5: 4BC37062C9C753C32A5AF1F4835D85C0
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Znanstveno delo |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FOV - Fakulteta za organizacijske vede
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | UNO-graph, line graph, bipartite graph, bipartite multigraph, graph algorithm |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Poslano v recenzijo: | 17.07.2025 |
|---|
| Datum sprejetja članka: | 03.09.2025 |
|---|
| Datum objave: | 05.09.2025 |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | 17 str. |
|---|
| Številčenje: | Vol. 13, iss. 17, [article no.] 2876 |
|---|
| PID: | 20.500.12556/DKUM-95222  |
|---|
| UDK: | 37.018.43:004:616-036.21 |
|---|
| COBISS.SI-ID: | 248174339 |
|---|
| DOI: | 10.3390/math13172876 |
|---|
| ISSN pri članku: | 2227-7390 |
|---|
| Datum objave v DKUM: | 09.09.2025 |
|---|
| Število ogledov: | 182 |
|---|
| Število prenosov: | 7 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
