Fixed-parameter complexity of \(\lambda\)-labelings
From MaRDI portal
Publication:5948961
DOI10.1016/S0166-218X(00)00387-5zbMath0982.05085OpenAlexW2184661648WikidataQ56505203 ScholiaQ56505203MaRDI QIDQ5948961
Jan Kratochvíl, Jiří Fiala, Ton Kloks
Publication date: 29 March 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00387-5
Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Related Items
\(L(p,q)\) labeling of \(d\)-dimensional grids ⋮ An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees ⋮ Computing L(p,1)-Labeling with Combined Parameters ⋮ A linear time algorithm for \(L(2,1)\)-labeling of trees ⋮ Cantor--Bernstein type theorem for locally constrained graph homomorphisms ⋮ Computational complexity of distance edge labeling ⋮ The complexity of \(L(p, q)\)-edge-labelling ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ Threshold-coloring and unit-cube contact representation of planar graphs ⋮ BCH codes and distance multi- or fractional colorings in hypercubes asymptotically ⋮ Facial \(L(2, 1)\)-edge-labelings of trees ⋮ \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\) ⋮ \(L(2, 1)\)-labeling of the Cartesian and strong product of two directed cycles ⋮ Parameterized complexity of distance labeling and uniform channel assignment problems ⋮ Fast exact algorithm for \(L(2,1)\)-labeling of graphs ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Graph covers: where topology meets computer science, and simple means difficult ⋮ Distance Constrained Labelings of Trees ⋮ Comparing Universal Covers in Polynomial Time ⋮ Distance three labelings of trees ⋮ Exact algorithms for \(L(2,1)\)-labeling of graphs ⋮ Locally constrained graph homomorphisms and equitable partitions ⋮ Unnamed Item ⋮ An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees ⋮ On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs ⋮ \(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs ⋮ \(L(2,1)\)-labeling of perfect elimination bipartite graphs ⋮ Computing role assignments of proper interval graphs in polynomial time ⋮ Locally constrained graph homomorphisms -- structure, complexity, and applications ⋮ Determining the \(L(2,1)\)-span in polynomial space ⋮ Unnamed Item ⋮ On Improved Exact Algorithms for L(2,1)-Labeling of Graphs ⋮ Computing Role Assignments of Proper Interval Graphs in Polynomial Time ⋮ Computing \(L(p, 1)\)-labeling with combined parameters ⋮ Labeling planar graphs with a condition at distance two ⋮ Fast Exact Algorithm for L(2,1)-Labeling of Graphs ⋮ On the computational complexity of partial covers of theta graphs ⋮ Distance constrained labelings of planar graphs with no short cycles ⋮ Graph labellings with variable weights, a survey ⋮ Complexity of (p,1)-total labelling ⋮ Systems of distant representatives ⋮ \(L(2,1)\)-labeling of direct product of paths and cycles ⋮ An exact algorithm for the channel assignment problem ⋮ The \(L(h,1,1)\)-labelling problem for trees ⋮ Computing role assignments of chordal graphs ⋮ The complexity of \(L(p, q)\)-edge-labelling ⋮ \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs ⋮ Comparing universal covers in polynomial time ⋮ Theory of computational complexity. Part 7. Transl. from the Russian ⋮ Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds ⋮ On \((s,t)\)-relaxed \(L(2,1)\)-labeling of graphs ⋮ On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT ⋮ On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT ⋮ On \(L(d,1)\)-labeling of Cartesian product of a cycle and a path ⋮ Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems ⋮ The complexity of the \(L(p,q)\)-labeling problem for bipartite planar graphs of small degree ⋮ On \(L(2,1)\)-labelings of Cartesian products of paths and cycles ⋮ \(\lambda \)-backbone colorings along pairwise disjoint stars and matchings ⋮ Distance constrained labelings of \(K_{4}\)-minor free graphs ⋮ Systems of pairs of \(q\)-distant representatives, and graph colorings ⋮ On circular-L(2, 1)-labellings of products of graphs ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree ⋮ A complete complexity classification of the role assignment problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Regular codes in regular graphs are difficult
- Relating path coverings to vertex labellings with a condition at distance two
- Covering regular graphs
- Labelling Graphs with a Condition at Distance 2
- Graph labeling and radio channel assignment
- Labeling Chordal Graphs: Distance Two Condition
- Algorithms for Square Roots of Graphs
- On the $\lambda$-Number of $Q_n $ and Related Graphs
- The $L(2,1)$-Labeling Problem on Graphs
