Recognizing hyperelliptic graphs in polynomial time

Jelco M. Bodewes, Hans L. Bodlaender, Gunther Cornelissen, Marieke van der Wegen

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

5 Citaten (Scopus)

Samenvatting

Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. We consider so-called hyperelliptic graphs (multigraphs of gonality 2) and provide a safe and complete set of reduction rules for such multigraphs, showing that we can recognize hyperelliptic graphs in time O(nlog n+ m), where n is the number of vertices and m the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph G admits an involution σ such that the quotient G/ ⟨ σ⟩ is a tree.

Originele taal-2Engels
TitelGraph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings
RedacteurenAndreas Brandstädt, Ekkehard Köhler, Klaus Meer
Plaats van productieCham
UitgeverijSpringer
Pagina's52-64
Aantal pagina's13
ISBN van elektronische versie978-3-030-00256-5
ISBN van geprinte versie978-3-030-00255-8
DOI's
StatusGepubliceerd - 1 jan 2018
Evenement44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018) - Cottbus, Duitsland
Duur: 27 jun 201829 jun 2018
https://www.wg2018.b-tu.de/

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11159 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres44th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG2018)
Verkorte titelWG2018
Land/RegioDuitsland
StadCottbus
Periode27/06/1829/06/18
Internet adres

Vingerafdruk

Duik in de onderzoeksthema's van 'Recognizing hyperelliptic graphs in polynomial time'. Samen vormen ze een unieke vingerafdruk.

Citeer dit