On the parameterized complexity of computing good edge-labelings

DOI10.1016/J.JCSS.2025.103752MaRDI QIDQ6859735zbMATH OpenFDO

Authors Davi de Andrade, Júlio Araújo, Laure Morelle, Ignasi Sau, Ana Silva

Publication date 11 February 2026

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2025.103752

zbMATH Keywords

good edge-labelingsparameterized complexitypolynomial kernelstructural parameterstreewidth

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A single-exponential time 2-approximation algorithm for treewidth
• Algorithmic meta-theorems for restrictions of treewidth
• An introduction to temporal graphs: an algorithmic perspective
• Connectivity and inference problems for temporal networks
• Directed acyclic graphs with the unique dipath property
• Eulerian walks in temporal graphs
• Feedback edge sets in temporal graphs
• Fundamentals of parameterized complexity
• Good edge-labelling of graphs
• scientific article; zbMATH DE number 961960 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• scientific article; zbMATH DE number 7788607 (Why is no real title available?)
• Kernel bounds for structural parameterizations of pathwidth
• Kernelization. Theory of parameterized preprocessing
• Mengerian graphs: characterization and recognition
• On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}
• On computing large temporal (unilateral) connected components
• On structural parameterizations of firefighting
• On the density of nearly regular graphs with a good edge-labeling
• On the maximum density of graphs with unique-path labelings
• Parameterized algorithms
• Parametrized complexity theory.
• Simple, strict, proper, happy: a study of reachability in temporal graphs
• Temporal network optimization subject to connectivity constraints
• The complexity of computing optimum labelings for temporal connectivity
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning
• Treewidth. Computations and approximations

This page was built for publication: On the parameterized complexity of computing good edge-labelings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6859735)